Pagini recente » Cod sursa (job #2615153) | Cod sursa (job #934753) | Cod sursa (job #2588841) | Cod sursa (job #320561) | Cod sursa (job #952686)
Cod sursa(job #952686)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream in ("atac.in");
ofstream out ("atac.out");
const int MAXN = 32010 * 2;
int N;
vector <int> Graf[MAXN];
int H[MAXN * 2], First[MAXN * 2], Lvl[MAXN * 2], Niv[MAXN * 2];
int RMQ[17][MAXN], V[MAXN], Seq[MAXN * 2];
int Log[MAXN];
int T[17][MAXN], DP[17][MAXN], Father[MAXN];
int now, now2;
void DFS (int nod, int lev)
{
++ now;
H[now] = nod;
Lvl[now] = lev;
Niv[nod] = lev;
First[nod] = now;
Seq[++ now2] = V[nod];
for (auto it = Graf[nod].begin (); it != Graf[nod].end (); ++ it){
DFS (*it, lev + 1);
++ now;
H[now] = nod;
Lvl[now] = lev;
}
Seq[++ now2] = V[nod];
}
void Build_Log ()
{
int i;
for (i = 2; i < MAXN; i ++)
Log[i] = Log[i / 2] + 1;
}
void Build_RMQ ()
{
int i, j, a, b;
for (i = 1; i <= now; i ++)
RMQ[0][i] = i;
for (j = 1; (1 << j) <= now; j ++)
for (i = 1; i + (1 << j) <= now; i ++){
a = RMQ[j - 1][i];
b = RMQ[j - 1][i + (1 << (j - 1))];
if (Lvl[a] <= Lvl[b])
RMQ[j][i] = a;
else
RMQ[j][i] = b;
}
}
int LCA (int nod1, int nod2)
{
nod1 = First[nod1];
nod2 = First[nod2];
if (nod2 < nod1)
swap (nod1, nod2);
int dif = nod2 - nod1 + 1;
int log = Log[dif];
int a, b;
a = RMQ[log][nod1];
b = RMQ[log][nod2 - (1 << log) + 1];
if (Lvl[a] <= Lvl[b])
return a;
else
return b;
}
void Build_Stramosi ()
{
int i, j;
for (i = 2; i <= N; i ++)
T[0][i] = Father[i], DP[0][i] = V[i];
for (i = 1; (1 << i) <= N; i ++)
for (j = 1; j <= N; j ++){
if ((1 << i) >= Niv[j])
continue;
T[i][j] = T[i - 1][T[i - 1][j]];
DP[i][j] = DP[i - 1][j];
if (DP[i - 1][T[i - 1][j]] < DP[i][j])
DP[i][j] = DP[i - 1][T[i - 1][j]];
}
}
int Query (int X, int Y)
{
int i, dif = Niv[X] - Niv[Y], Ans = (1 << 30);
for (i = 0; (1 << i) <= dif; i ++)
if (dif & (1 << i)){
if (DP[i][X] < Ans)
Ans = DP[i][X];
X = T[i][X];
}
return Ans;
}
int Solve (int X, int Y)
{
if (X == Y)
return 0;
int lca, a, b;
lca = H[LCA (X, Y)];
a = Query (X, lca);
b = Query (Y, lca);
return min (a, b);
}
int main()
{
int M, P, i, a, X, Y, Z, A, B, C, D, newX, newY;
in >> N >> M >> P;
for (i = 2; i <= N; i ++){
in >> Father[i] >> V[i];
Graf[Father[i]].push_back (i);
}
V[1] = (1 << 30);
in >> X >> Y >> A >> B >> C >> D;
DFS (1, 1);
Build_Log ();
Build_RMQ ();
Build_Stramosi ();
for (i = 1; i <= M; i ++)
{
Z = Solve (X, Y);
if (i >= M - P + 1)
out << Z << "\n";
newX = (X * A + Y * B) % N + 1;
newY = (Y * C + Z * D) % N + 1;
X = newX;
Y = newY;
}
return 0;
}