Pagini recente » Cod sursa (job #1515096) | Cod sursa (job #2425167) | Cod sursa (job #492679) | Cod sursa (job #2411974) | Cod sursa (job #974866)
Cod sursa(job #974866)
#include <fstream>
#include <vector>
#include <list>
using namespace std;
#define pb push_back
#define last (int)(E.size()-1)
vector <list <int> > g;
vector <vector <int> > rmq, t, dmin;
vector <int> tata, F, E, L, v, bp;
int n, m, X, Y, A, B, C, D, p;
ifstream fin ("atac.in");
ofstream fout ("atac.out");
int cmp(int a, int b) {
return ((L[a] < L[b]) ? a : b);
}
void Resize() {
g.resize(n+1);
tata.resize(n+1);
E.reserve(2*n+10);
L.reserve(2*n+10);
F.resize(n+1);
v.resize(n+1);
}
void dfs (int x, int val) {
E.pb(x);
L.pb(val);
F[x] = last;
for (list <int> :: iterator it = g[x].begin(); it != g[x].end(); ++it) {
dfs(*it, val + 1);
E.pb(x);
L.pb(val);
}
}
void RMQ() {
bp.resize(last+1);
for (int i = 2; i <= last; ++i)
bp[i] = bp[i/2] + 1;
rmq.resize(bp[last] + 1);
dmin.resize(bp[n] + 1);
t.resize(bp[n] + 1);
for (int i = 0; i <= bp[last]; ++i) {
if (i <= bp[n]) {
t[i].resize(n+1);
dmin[i].resize(n+1);
}
rmq[i].resize(last+1);
}
for (int i = 1; i <= last; ++i) {
if (i <= n) {
t[0][i] = tata[i];
dmin[0][i] = v[i];
}
rmq[0][i] = i;
}
for (int i = 1; i <= bp[last]; ++i)
for (int j = 1; j <= last - (1 << i) + 1; ++j)
rmq[i][j] = cmp(rmq[i-1][j], rmq[i-1][j + (1 << (i - 1))]);
for (int i = 1; i <= bp[n]; ++i)
for (int j = 1; j <= n; ++j) {
t[i][j] = t[i-1][t[i-1][j]];
dmin[i][j] = min (dmin[i-1][j], dmin[i-1][t[i-1][j]]);
}
}
int query(int x, int y) {
int dif = L[F[x]] - L[F[y]], res = 0x3f3f3f3f;
for (int i = 0; i <= bp[dif]; ++i)
if ((1 << i) & dif) {
res = min (res, dmin[i][x]);
x = t[i][x];
}
return res;
}
int LCA(int x, int y) {
int a = F[x], b = F[y];
if (a > b)
swap (a, b);
int pow = bp[b - a + 1];
return E[cmp(rmq[pow][a], rmq[pow][b + 1 - (1 << pow)])];
}
int main() {
fin >> n >> m >> p;
Resize();
for (int i = 2; i <= n; ++i) {
fin >> tata[i] >> v[i];
g[tata[i]].pb (i);
}
fin >> X >> Y >> A >> B >> C >> D;
E.pb(0);
L.pb(0);
dfs(1, 0);
RMQ();
while (m--) {
int lca = LCA(X, Y), Z = 0x3f3f3f3f;
if (X != Y) {
Z = min (Z, query (X, lca));
Z = min (Z, query (Y, lca));
}
else
Z = 0;
if (m < p)
fout << Z << "\n";
X = (X * A + Y * B) % n + 1;
Y = (Y * C + Z * D) % n + 1;
}
}