Cod sursa(job #779445)

Utilizator ionut_blesneagIonut Blesneag ionut_blesneag Data 17 august 2012 18:14:24
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include<cstdio>
#include<algorithm>
#include<list>
using namespace std;

int N,M,P,i,j,U,V,X,Y,Z,A,B,C,D,Grandpa;
struct road {int nod; int cost;};
list<road> L[32001];
int level[32001],first[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;
   }
parcurgere_euleriana(1,0);   

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++)
{Z=lca(first[X],first[Y]);
if(i>M-P)
  printf("%d\n",Z);
X=((long long)(X*A))%N+((long long)(Y*B))%N+1;
Y=((long long)(Y*C))%N+((long long)(Z*D))%N+1;}
 
return 0;}