Pagini recente » Cod sursa (job #409749) | Cod sursa (job #2176175) | Cod sursa (job #2466867) | Cod sursa (job #2473408) | Cod sursa (job #2499770)
#include <fstream>
#include <vector>
#include <cmath>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int NMAX = 32000;
const int LOGMAX = 16;
int N, M, P, res;
int X, Y, A, B, C, D;
vector < pair <int, int> > g[NMAX + 5];
int h[NMAX + 5], firstAp[NMAX + 5];
int ancestor[LOGMAX + 2][NMAX + 5], costMinUp[LOGMAX + 2][NMAX + 5];
vector < int > rmq[LOGMAX + 5];
void dfs(int node, int dad)
{
h[node] = h[dad] + 1;
for(int i = 1; i <= LOGMAX; i++)
if((1 << i) > h[node])
break;
else
{
ancestor[i][node] = ancestor[i - 1][ancestor[i - 1][node]];
costMinUp[i][node] = min(costMinUp[i - 1][node], costMinUp[i - 1][ancestor[i - 1][node]]);
}
firstAp[node] = rmq[0].size();
rmq[0].push_back(node);
for(auto it : g[node])
if(it.first != dad)
{
dfs(it.first, node);
ancestor[0][it.first] = node;
costMinUp[0][it.first] = it.second;
rmq[0].push_back(node);
}
}
int Merge(int A, int B)
{
if(h[A] < h[B])
return A;
return B;
}
void buildRmq()
{
for(int i = 1; i <= LOGMAX; i++)
if((1 << i) > (int)rmq[0].size())
break;
else
{
for(int j = 0; j < (int)rmq[0].size(); j++)
if(j + (1 << i) > (int)rmq[0].size())
break;
else
rmq[i].push_back(Merge(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]));
}
}
int Query(int A, int B)
{
int AA = A, BB = B;
A = firstAp[A];
B = firstAp[B];
if(A > B) swap(A, B);
int l = log2(B - A + 1);
int lca = Merge(rmq[l][A], rmq[l][B - (1 << l) + 1]);
int minEdgeFromA = 1e6, minEdgeFromB = 1e6;
int hA = h[AA], hB = h[BB], hlca = h[lca];
for(int i = LOGMAX; i >= 0; i--)
{
if(hA - (1 << i) >= hlca)
{
minEdgeFromA = min(minEdgeFromA, costMinUp[i][AA]);
AA = ancestor[i][AA];
hA = h[AA];
}
if(hB - (1 << i) >= hlca)
{
minEdgeFromB = min(minEdgeFromB, costMinUp[i][BB]);
BB = ancestor[i][BB];
hB = h[BB];
}
}
return min(minEdgeFromA, minEdgeFromB);
}
int main()
{
fin >> N >> M >> P;
for(int i = 2; i <= N; i++)
{
int x, y;
fin >> x >> y;
g[i].push_back({x, y});
g[x].push_back({i, y});
}
fin >> X >> Y >> A >> B >> C >> D;
dfs(1, 0);
buildRmq();
for(int i = 1; i <= M; i++)
{
if(X == Y)
res = 0;
else
res = Query(X, Y);
if(i >= M - P + 1)
fout << res << '\n';
int newX = (1LL * X * A + Y * B) % (N + 1), newY = (Y * C + res * D) % (N + 1);
X = newX;
Y = newY;
}
return 0;
}