Pagini recente » Cod sursa (job #1551041) | Links | Profil oldatlantian | Profil oldatlantian | Cod sursa (job #2971352)
#include <fstream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cassert>
#define infile "atac.in"
#define outfile "atac.out"
using namespace std;
const int MAX_N = 33005;
const int MAX_LOG = 17;
const int INF = 2000000000;
int n;
int level[MAX_N];
int p_current = 0, p_start[MAX_N], p_end[MAX_N];
int parent[MAX_LOG][MAX_N], cost[MAX_LOG][MAX_N];
vector<int> tree[MAX_N];
void dfs(int node, int _level = 1)
{
level[node] = _level;
p_start[node] = ++p_current;
for (int adj : tree[node])
{
dfs(adj, _level + 1);
}
p_end[node] = ++p_current;
}
bool is_ancestor(int x, int y)
{
return p_start[x] <= p_start[y] && p_end[y] <= p_end[x];
}
void calcAncestors()
{
for (int i = 1; (1 << i) <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
cost[i][j] = min(cost[i - 1][j], cost[i - 1][parent[i - 1][j]]);
parent[i][j] = parent[i - 1][parent[i - 1][j]];
}
}
}
int getLca(int x, int y)
{
if (is_ancestor(x, y))
{
return x;
}
if (is_ancestor(y, x))
{
return y;
}
for (int p = MAX_LOG - 1; p >= 0; --p)
{
int z = parent[p][x];
if (z != 0 && !is_ancestor(z, y))
{
x = z;
}
}
return parent[0][x];
}
int getCost(int x, int y)
{
if (x == y)
return 0;
int lca = getLca(x, y);
int minimum = INF;
for (int node : {x, y})
{
int diff = level[node] - level[lca];
for (int p = MAX_LOG - 1; p >= 0; --p)
{
if (diff >= (1 << p))
{
diff -= (1 << p);
minimum = min(minimum, cost[p][node]);
node = parent[p][node];
}
}
}
return minimum;
}
int main()
{
ifstream fin(infile);
ofstream fout(outfile);
int m, p;
fin >> n >> m >> p;
for (int i = 2; i <= n; ++i)
{
fin >> parent[0][i] >> cost[0][i];
tree[parent[0][i]].push_back(i);
}
dfs(1);
calcAncestors();
int node1, node2, A, B, C, D;
fin >> node1 >> node2 >> A >> B >> C >> D;
for (int i = 1; i <= m; ++i)
{
int sol = getCost(node1, node2);
if (m - i + 1 <= p)
fout << sol << '\n';
node1 = (node1 * A + node2 * B) % n + 1;
node2 = (node2 * C + sol * D) % n + 1;
}
return 0;
}