Cod sursa(job #779501)

Utilizator ionut_blesneagIonut Blesneag ionut_blesneag Data 17 august 2012 20:57:20
Problema Atac Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include<cstdio>
#include<algorithm>
#include<list>
using namespace std;

const int inf=100001;
int N,M,P,i,j,U,V,X,Y,Z,A,B,C,D;
int stramos,min_road,xx,yy;
struct road {int nod; int cost;};
list<road> L[32001];
int level[32001],first[32001],t[32001],ct[32001];

int eulerian[1000001],size_eul;
int rmq[20][1000001];
int pozx, pozy, lg[1000001];

int minim(int aa, int bb)
{if(level[aa]<level[bb])
 return aa;
return bb;}

int maxim(int aa, int bb)
{if(level[aa]>level[bb])
 return aa;
return bb;}
 
int lca(int x, int y)
{int ancestor;
int k=lg[max(x,y)-min(x,y)+1];
ancestor=minim(rmq[k][min(x,y)],rmq[k][max(x,y)-(1<<k)+1]);
return ancestor;}

void parcurgere_euleriana(int x,int val)
{size_eul++;
eulerian[size_eul]=x;
rmq[0][size_eul-1]=val;
first[x]=size_eul;
list<road>::iterator it;
for(it=L[x].begin();  it!=L[x].end(); it++)
  {road q;   q=*it;
   parcurgere_euleriana(q.nod,q.cost);
   size_eul++;
   eulerian[size_eul]=x;
   rmq[0][size_eul-1]=q.cost;
   }        
}

int main()
{freopen("atac.in","r",stdin);
freopen("atac.out","w",stdout);
scanf("%d %d %d",&N,&M,&P);
level[1]=1;
for(i=2; i<=N; i++)
  {scanf("%d %d",&U,&V);
   road p;
   p.nod=i;  p.cost=V;
   L[U].push_back(p);
   level[i]=level[U]+1;
   t[i]=U;  ct[i]=V;
   }
parcurgere_euleriana(1,0);   

for(j=1; j<=size_eul; j++)
 rmq[0][j]=eulerian[j];

for(j=2; j<=size_eul; j++) 
 lg[j]=lg[j/2]+1;

for(i=1; i<=lg[size_eul-1]; i++)
 for(j=1; j<=(size_eul-(1<<i)); j++)
   rmq[i][j]=minim(rmq[i-1][j],rmq[i-1][j+(1<<(i-1))]);

scanf("%d %d %d %d %d %d",&X,&Y,&A,&B,&C,&D); 
for(i=1; i<=M; i++)
{stramos=lca(first[X],first[Y]);
xx=X;   yy=Y;  min_road=inf;
while(xx!=stramos)
{if(ct[xx]<min_road)
   min_road=ct[xx];
 xx=t[xx];}
while(yy!=stramos)
{if(ct[yy]<min_road)
   min_road=ct[yy];
 yy=t[yy];} 
Z=min_road; 
if(i>M-P)
  printf("%d\n",Z);
X=(X*A+Y*B)%N+1;
Y=(Y*C+Z*D)%N+1;}
 
return 0;}