Pagini recente » Cod sursa (job #281247) | Cod sursa (job #1271863) | Cod sursa (job #2967967) | Cod sursa (job #672380) | Cod sursa (job #2409967)
#include <bits/stdc++.h>
#define Dim 32007
#define MAX 2000000000
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");
int N,M,P,X,Y,X1,Y1,A,B,C,D,Z,a,b;
int E[3*Dim],Prim[Dim],G[3*Dim],cnt,Level[Dim];
int rmq[20][Dim],cost[20][Dim],T[20][Dim],lca;
typedef pair<int,int> pi;
bool viz[Dim];
vector < pi > V[Dim];
set < pi > S[Dim];
set < pi > ::iterator it;
void DFS(int nod,int niv)
{
viz[nod]=1;
Level[nod]=niv;
G[++cnt]=niv;
E[cnt]=nod;
Prim[nod]=cnt;
for(unsigned int i=0;i<V[nod].size();i++)
{
int vecin=V[nod][i].first;
if(!viz[vecin])
{
cost[0][vecin]=V[nod][i].second;
T[0][vecin]=nod;
DFS(vecin,niv+1);
E[++cnt]=nod;
G[cnt]=niv;
}
}
}
void RMQ()
{
for(int i=1;i<=cnt;i++) rmq[0][i]=i;
for(int i=1;(1<<i)<=cnt;i++)
for(int j=1;j+(1<<i)-1<=cnt;j++)
{
int a=rmq[i-1][j];
int b=rmq[i-1][j+(1<<(i-1))];
if(G[a]<=G[b]) rmq[i][j]=a;
else rmq[i][j]=b;
}
}
void COST()
{
for(int i=1;(1<<i)<=N;i++)
for(int j=1;j<=N;j++)
{
T[i][j]=T[i-1][T[i-1][j]];
cost[i][j]=min(cost[i-1][j],cost[i-1][T[i-1][j]]);
}
}
int LCA(int poza,int pozb)
{
if(poza>pozb)
{
swap(poza,pozb);
}
int dif=log2(pozb-poza+1);
if(G[rmq[dif][poza]]<=G[rmq[dif][pozb-(1<<dif)+1]])
{
return E[rmq[dif][poza]];
}
else
{
return E[rmq[dif][pozb-(1<<dif)+1]];
}
}
int Solve(int x,int y)
{
if(x==y) return MAX;
int d=log2(Level[x]-Level[y]);
if(Level[T[d][x]]==Level[y])
return cost[d][x];
else
return min(cost[d][x],Solve(T[d][x],y));
}
int main()
{
f>>N>>M>>P;
for(int i=2;i<=N;i++)
{
f>>a>>b;
V[i].push_back({a,b});
V[a].push_back({i,b});
}
DFS(1,1);
RMQ();
COST();
f>>X>>Y>>A>>B>>C>>D;
for(int i=1;i<=M;i++)
{
if(X!=Y)
{
lca=LCA(Prim[X],Prim[Y]);
Z=MAX;
Z=min(Z,Solve(X,lca));
Z=min(Z,Solve(Y,lca));
}
else Z=0;
if(i>=M-P+1) g<<Z<<'\n';
X1=(A*X+B*Y)%N; X1++;
Y1=(Y*C+D*Z)%N; Y1++;
X=X1;
Y=Y1;
}
return 0;
}