Pagini recente » Atasamentele paginii Clasament kys | Cod sursa (job #128412) | Statistici Tudor Stefania (stefaniatudor) | Istoria paginii utilizator/canciu.carmen | Cod sursa (job #1213718)
#include <fstream>
#include <vector>
using namespace std;
ifstream f("atac.in");
ofstream g("atac.out");
int N,M,P;
int A,B,C,D,X,Y,Result[500005];
vector <int> G[32005],G1[32005];
vector <int> Cost[32005];
int Min[25][32005],Father[25][32005],level;
bool Use2[32005],Use[32005];
int ind,First[32005],Level[32005<<1],counter;
int minimum_result[25][32005<<2],log[32005<<1],Log2[32005];
void Read()
{
f>>N>>M>>P;
for(int i=0;i<=20;i++)
for(int j=0;j<=32000;j++)
Min[i][j]=(1<<30);
int i;
for(i=2;i<=N;i++)
{
int U,V;
f>>U>>V;
G1[U].push_back(i);
G1[i].push_back(U);
Cost[i].push_back(V);
Cost[U].push_back(V);
}
f>>X>>Y>>A>>B>>C>>D;
}
void DFS1(int node)
{
Use2[node]=1;
for(int i=0;i<G1[node].size();i++)
{
int neighbour=G1[node][i],cost=Cost[node][i];
if(Use2[neighbour]==0)
{
G[node].push_back(neighbour);
Father[0][neighbour]=node;
Min[0][neighbour]=cost;
DFS1(neighbour);
}
}
}
void Calculate_log2()
{
int i=2,next=2;
while(i<=ind)
{
if(i!=next)
log[i]=log[i-1];
else
{
log[i]=log[i-1]+1;
next=i*2;
}
i++;
}
}
void Build_matrichs()
{
int i,j,forward=1;
for(i=1;i<=log[ind];i++)
{
for(j=1;j<=ind-forward*2+1;j++)
{
if(Level[minimum_result[i-1][j]]<Level[minimum_result[i-1][j+forward]])
minimum_result[i][j]=minimum_result[i-1][j];
else
minimum_result[i][j]=minimum_result[i-1][j+forward];
}
forward*=2;
}
}
int RMQ(int x,int y)
{
int i;
int how_much=log[y-x+1];
if(log[y-x]==how_much-1)
return minimum_result[log[y-x+1]][x];
else
{
if(Level[minimum_result[how_much][x]]<Level[minimum_result[how_much][y-(1<<how_much)+1]])
return minimum_result[how_much][x];
else
return minimum_result[how_much][y-(1<<how_much)+1];
}
}
void DFS(int nod)
{
minimum_result[0][++ind]=nod;
if(Use[nod]==0)
First[nod]=ind,counter++;
Use[nod]=1;
Level[nod]=level;
level++;
for(unsigned int i=0;i<G[nod].size();i++)
{
int vecin=G[nod][i];
if(Use[vecin]==0)
{
DFS(vecin);
if(counter<N)
minimum_result[0][++ind]=nod;
}
}
level--;
}
void Precalculate()
{
for(int i=1;(1<<i)<=N;i++)
for(int j=1;j<=N;j++)
Father[i][j]=Father[i-1][Father[i-1][j]];
for(int i=1;(1<<i)<=N;i++)
for(int j=1;j<=N;j++)
Min[i][j]=min(Min[i-1][j],Min[i-1][Father[i-1][j]]);
for(int i=2;i<=N;i++)
Log2[i]=Log2[i/2]+1;
}
int minResult(int x,int y)
{
int dist=Level[x]-Level[y];
int result=(1<<30);
while(dist>0)
{
int k=Log2[dist];
result=min(result,Min[dist][x]);
x=Father[k][x];
dist-=(1<<k);
}
return result;
}
void Browse()
{
int i;
int x=X,y=Y;
for(i=1;i<=M;i++)
{
int aux1=x,aux2=y;
if(First[x]>First[y])
swap(x,y);
int lca=RMQ(First[x],First[y]);
int Z=min(minResult(x,lca),minResult(y,lca));
Result[i]=Z;
x=(1LL*aux1*A)%N+(1LL*aux2*B)%N+1;
y=(1LL*aux2*C)%N+(1LL*Z*D)%N+1;
}
}
int main()
{
Read();
DFS1(1);
DFS(1);
Calculate_log2();
Build_matrichs();
Precalculate();
Browse();
for(int i=M-P+1;i<=M;i++)
g<<Result[i]<<"\n";
return 0;
}