Pagini recente » Cod sursa (job #2069181) | Cod sursa (job #2840947) | Cod sursa (job #1558598) | Cod sursa (job #2037480) | Cod sursa (job #2921546)
#include <bits/stdc++.h>
#define NMAX 32008
using namespace std;
ifstream fin ("atac.in");
ofstream fout ("atac.out");
int n, m, p;
int X, Y, Z, A, B, C, D;
vector < pair <int, int> > G[NMAX], euler;
int first[NMAX*2], dp[NMAX*2][50], logg[NMAX*2], h[NMAX], dp2[NMAX*2][50], nodd[NMAX], str[NMAX*2][50];
void citire();
void DFS(int nod, int tata);
void DFS_euler(int nod, int tata);
void RMQ();
void logaritm();
int query(int x, int y);
int main()
{
citire();
logaritm();
h[0] = -1;
DFS_euler(1, 0);
RMQ();
for (int i = 1; i <= m; i++)
{
int min1 = 1e9, min2 = 1e9, min3 = 1e9, min4 = 1e9;
int lca = query(X, Y);
lca = euler[lca].first;
int lg = h[X] - h[lca];
if (lg)
{
int sz = logg[lg];
min1 = dp2[X][sz];
int nr = lg - (1<<sz);
int stramos = X;
while (nr)
{
int sz2 = logg[nr];
stramos = str[stramos][sz2];
nr = nr - (1<<sz2);
}
min2 = dp2[stramos][sz];
}
lg = h[Y] - h[lca];
if (lg)
{
int sz = logg[lg];
min3 = dp2[Y][sz];
int nr = lg - (1<<sz);
int stramos = Y;
while (nr)
{
int sz2 = logg[nr];
stramos = str[stramos][sz2];
nr = nr - (1<<sz2);
}
min4 = dp2[stramos][sz];
}
Z = min(min1, min(min2, min(min3, min4)));
if (Z == 1e9)
Z = 0;
if (i >= m - p + 1)
fout << Z << '\n';
X = (X*A + Y*B) % n + 1;
Y = (Y*C + Z*D) % n + 1;
}
return 0;
}
void citire()
{
int x, y;
fin >> n >> m >> p;
for (int i = 2; i <= n; i++)
{
fin >> x >> y;
G[x].push_back({i, y});
G[i].push_back({x, y});
}
fin >> X >> Y >> A >> B >> C >> D;
}
void DFS_euler(int nod, int tata)
{
first[nod] = euler.size();
h[nod] = h[tata] + 1;
nodd[h[nod]] = nod;
euler.push_back({nod, h[nod]});
for (auto fiu : G[nod])
if (fiu.first != tata)
{
if (fiu.first == 6)
int ok = 1;
dp2[fiu.first][0] = fiu.second;
for (int j = 1; h[nod]+1-(1<<j)>=0; j++)
{
int stramos = nodd[h[nod]+1-(1<<(j-1))];
dp2[fiu.first][j] = min(dp2[fiu.first][j-1], dp2[stramos][j-1]);
str[fiu.first][j] = str[stramos][j-1];
}
DFS_euler(fiu.first, nod);
euler.push_back({nod, h[nod]});
}
}
void RMQ()
{
int len = euler.size();
for (int i = 0; i < len; i++)
dp[i][0] = i;
for (int j = 1; (1 << j) <= len; j++)
for (int i = 0; i + (1<<j) <= len; i++)
{
int poz1 = dp[i][j-1];
int min1 = euler[poz1].second;
int poz2 = dp[i+(1<<(j-1))][j-1];
int min2 = euler[poz2].second;
if (min1 < min2)
dp[i][j] = poz1;
else
dp[i][j] = poz2;
}
}
void logaritm()
{
logg[1] = 0;
for (int i = 2; i <= 2 * n; i++)
logg[i] = 1 + logg[i/2];
}
int query(int x, int y)
{
int l = first[x];
int r = first[y];
if (l > r)
swap(l, r);
int lg = r - l + 1;
int sz = logg[lg];
int poz1 = dp[l][sz];
int min1 = euler[poz1].second;
int poz2 = dp[r+1-(1<<(sz))][sz];
int min2 = euler[poz2].second;
if (min1 < min2)
return poz1;
else
return poz2;
}