Cod sursa(job #779482)

Utilizator ionut_blesneagIonut Blesneag ionut_blesneag Data 17 august 2012 19:45:30
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 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 first[32001];

int eulerian[1000001],size_eul;
int rmq[20][1000001];
int pozx, pozy, lg[1000001];
 
int lca(int x, int y)
{int cost_min;
int k=lg[max(x,y)-min(x,y)];
cost_min=min(rmq[k][min(x,y)],rmq[k][max(x,y)-(1<<k)]);
return cost_min;}

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);
for(i=2; i<=N; i++)
  {scanf("%d %d",&U,&V);
   road p;
   p.nod=i;  p.cost=V;
   L[U].push_back(p);
   }
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]=min(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+Y*B))%N+1;
Y=((long long)(Y*C+Z*D))%N+1;}
 
return 0;}