Pagini recente » Cod sursa (job #187971) | Cod sursa (job #2075873) | Cod sursa (job #1207573) | Cod sursa (job #2584883) | Cod sursa (job #2351809)
#include <bits/stdc++.h>
using namespace std;
ifstream in("atac.in");
ofstream out("atac.out");
int n, m, p, x, c, rmq[20][64100], mn[20][32100], st[64100], viz[32100], niv[32100], vf, dp[20][32100], pos[32100], cost[32100], dad[32100];
int X, Y, A, B, C, D, toto;
vector <int> v[32100], sol;
void dfs(int x, int lvl) {
viz[x] = 1;
st[++vf] = x;
pos[x] = vf;
niv[x] = lvl;
for (auto y : v[x])
if (!viz[y]) {
dfs(y, lvl + 1);
st[++vf] = x;
}
}
void build() {
for (int i = 1; i <= vf; i++)
rmq[0][i] = st[i];
int sz = log2(vf);
for (int i = 1; i <= sz; i++)
for (int j = 1; j <= vf; j++)
rmq[i][j] = (niv[rmq[i - 1][j]] < niv[rmq[i - 1][j + (1 << (i - 1))]] ? rmq[i - 1][j] : rmq[i - 1][j + (1 << (i - 1))]);
}
void build2() {
for (int i = 1; i <= n; i++)
mn[0][i] = cost[i], dp[0][i] = dad[i];
for (int i = 1; i <= 16; i++)
for (int j = 1; j <= n; j++)
mn[i][j] = min(mn[i - 1][j], mn[i - 1][dp[i - 1][j]]);
for (int i = 1; i <= 16; i++)
for (int j = 1; j <= n; j++)
dp[i][j] = dp[i - 1][dp[i - 1][j]];
}
void solve(int x, int y) {
int xx = x, yy = y;
x = pos[x];
y = pos[y];
if (x > y)
swap(x, y);
int sz = log2(y - x + 1);
int p = (niv[rmq[sz][x]] < niv[rmq[sz][y - (1 << sz) + 1]] ? rmq[sz][x] : rmq[sz][y - (1 << sz) + 1]);
toto = INT_MAX;
int d = niv[xx] - niv[p];
for (int i = 0; i <= 16; i++)
if (d & (1 << i)) {
toto = min(toto, mn[i][xx]);
xx = dp[i][xx];
}
d = niv[yy] - niv[p];
for (int i = 0; i <= 16; i++)
if (d & (1 << i)) {
toto = min(toto, mn[i][yy]);
yy = dp[i][yy];
}
if (toto == INT_MAX)
toto = 0;
}
int main() {
in >> n >> m >> p;
for (int i = 2; i <= n; i++) {
in >> x >> c;
v[x].push_back(i);
cost[i] = c;
dad[i] = x;
}
dfs(1, 1);
build();
build2();
in >> X >> Y >> A >> B >> C >> D;
for (int i = 1; i <= m; i++) {
solve(X, Y);
int xp, yp;
xp = (X * A + Y * B) % n + 1LL;
yp = (Y * C + toto * D) % n + 1LL;
X = xp;
Y = yp;
if (i > m - p)
sol.push_back(toto);
}
for (auto i : sol)
out << i << '\n';
return 0;
}