Cod sursa(job #779565)

Utilizator ionut_blesneagIonut Blesneag ionut_blesneag Data 18 august 2012 00:56:01
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 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];
int a[20][250001],ct[20][250001];
int k1,k2,dif1,dif2;

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;
   a[0][i]=U;  ct[0][i]=V;
   }
   
for(j=1; j<=N; j++)
   for(i=1; i<=18; i++)
     {if(a[i-1][a[i-1][j]])
      {a[i][j]=a[i-1][a[i-1][j]];
       ct[i][j]=min(ct[i-1][a[i-1][j]],ct[i-1][j]);}
      else 
        break;} 
   
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;
dif1=level[X]-level[stramos];
dif2=level[Y]-level[stramos];

while(dif1)
{k1=lg[dif1];
if(min_road>ct[k1][xx])
  min_road=ct[k1][xx];
xx=a[k1][xx];  
dif1=dif1-(1<<k1);  
}

while(dif2)
{k2=lg[dif2];
if(min_road>ct[k2][yy])
  min_road=ct[k2][yy];
yy=a[k2][yy];  
dif2=dif2-(1<<k2);  
}

if(X==Y)
   Z=0;
else   
   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;}