Pagini recente » Cod sursa (job #263570) | Cod sursa (job #2657262) | Cod sursa (job #2746672) | Cod sursa (job #2459542) | Cod sursa (job #1674558)
# include <bits/stdc++.h>
# define NR 35000
# define INF 999999999
# define DIM 17
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");
vector <int> v[NR];
int i,j,n,m,A,B,C,D,X,Y,Z,niv[NR],Q,P,x,cost;
int best[NR][DIM], T[NR][DIM];
void DFS (int k, int nivel) {
niv[k]=nivel;
for (int i=1; i<DIM; ++i) {
T[k][i]=T[T[k][i-1]][i-1];
best[k][i]=min(best[k][i-1], best[T[k][i-1]][i-1]);
}
for (auto &x: v[k]) //daca nu am mai trecut pe aici
DFS (x, nivel+1);
}
int query (int X, int Y) {
int minim=INF;
if (X==Y) return 0;
if (niv[X] < niv[Y]) swap(X, Y);
for (int i=DIM-1; i>=0; --i)
if (niv[X] - (1<<i)>=niv[Y]) {
minim=min(minim, best[X][i]);
X=T[X][i];
}
for (int i=DIM-1; i>=0; --i) {
if (T[X][i]!=T[Y][i]) {
minim=min(minim, best[X][i]);
minim=min(minim, best[Y][i]);
X=T[X][i];
Y=T[Y][i];
}
}
if (X!=Y) {
minim=min(minim, min(best[X][0], best[Y][0]));
}
return minim;
}
int main ()
{
f>>n>>Q>>P;
for (i=2; i<=n; ++i) {
f>>x>>cost;
T[i][0]=x; best[i][0]=cost;
v[x].push_back(i);
}
for (int i=0; i<DIM; ++i) best[0][i]=INF;
best[1][0]=INF; DFS (1, 1);
f>>X>>Y>>A>>B>>C>>D;
for (i=1; i<=Q; ++i) {
Z=query (X, Y);
if (i>=Q - P + 1) g<<Z<<"\n";
X=(X*A + Y*B)%n + 1;
Y=(Y*C + Z*D)%n + 1;
}
return 0;
}