Pagini recente » Cod sursa (job #1515188) | Cod sursa (job #2872184) | Cod sursa (job #208486) | Cod sursa (job #1308583) | Cod sursa (job #2974951)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int NMAX = 33007;
const int LOGMAX = 20;
int n, m, p;
int level[NMAX], pcurent, pstart[NMAX], pend[NMAX], parent[LOGMAX][NMAX], cost[LOGMAX][NMAX];
vector<vector<int>> tree(NMAX);
bool isdad(int x, int y)
{
return pstart[x] <= pstart[y] && pend[y] <= pend[x];
}
void calculeazatata()
{
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 _lca(int x, int y)
{
if (isdad(x, y))
return x;
if (isdad(y, x))
return y;
for (int p = LOGMAX - 1; p >= 0; --p)
{
int z = parent[p][x];
if (z != 0 && !isdad(z, y))
{
x = z;
}
}
return parent[0][x];
}
void dfs(int node, int lvl = 1)
{
level[node] = lvl;
pstart[node] = ++pcurent;
for (int vecin: tree[node])
{
dfs(vecin, lvl + 1);
}
pend[node] = ++pcurent;
}
int getCost(int x, int y)
{
if (x == y)
return 0;
int lca = _lca(x, y);
int minimum = INT_MAX;
for (int node: {x, y})
{
int diff = level[node] - level[lca];
for (int p = LOGMAX - 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()
{
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);
calculeazatata();
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;
}