Cod sursa(job #80795)

Utilizator VmanDuta Vlad Vman Data 29 august 2007 23:59:59
Problema Atac Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <stdio.h>
#include <vector>
using namespace std;

#define Nmax 32768
#define logN 17
#define infinit 0x3f3f3f3f
#define radacina 1

int N,M,P,U,V,X,Y,A,B,C,D;
int i,aux,parinte[logN][Nmax],cmin[logN][Nmax],nivel[Nmax],maxdepth;
int euler[2*Nmax],pozitie[Nmax],cmsc[logN+1][2*Nmax];
vector<int> g[Nmax];

void inline citire()
{
 freopen("atac.in","r",stdin);
 scanf("%d %d %d",&N,&M,&P);
 for (i=2;i<=N;++i)
     {
     scanf("%d %d",&U,&V);
     parinte[0][i]=U;
     cmin[0][i]=V;
     g[U].push_back(i);
     }
 scanf("%d %d %d %d %d %d",&X,&Y,&A,&B,&C,&D);
 fclose(stdin);
}

void dfs(int nod,int depth)
{
 vector<int>::iterator i,fin=g[nod].end();
 maxdepth=(depth>maxdepth?depth:maxdepth);
 euler[++euler[0]]=nod;
 pozitie[nod]=euler[0];
 nivel[nod]=depth++;
 for (i=g[nod].begin();i<fin;++i)
     {
      dfs(*i,depth);
      euler[++euler[0]]=nod;
     }
}

int lca(int X,int Y)
{
 int i,pw,diferenta=pozitie[Y]-pozitie[X];
 for (i=0,pw=1;(pw<<1)<=diferenta;++i,pw<<=1);
 if (nivel[cmsc[i][pozitie[X]]]<nivel[cmsc[i][pozitie[Y]-pw]]) return cmsc[i][pozitie[X]];
    else return cmsc[i][pozitie[Y]-pw];
}

int solve(int X,int Y)
{
 int s,p,minim;
 if (pozitie[X]<pozitie[Y]) s=lca(X,Y);
    else s=lca(Y,X);
 minim=infinit;
 p=logN;
 while (X!=s)
       {
        while ((1<<(p-1))>nivel[s]-nivel[X])
              --p;
        minim=(cmin[p][X]<minim?cmin[p][X]:minim);
        X=parinte[p][X];
       }
 p=logN;
 while (Y!=s)
       {
        while ((1<<(p-1))>nivel[s]-nivel[Y])
              --p;
        minim=(cmin[p][Y]<minim?cmin[p][Y]:minim);
        Y=parinte[p][Y];
       }
 return minim;
}

void stramosi()
{
 int i,j,pw;
 for (i=0;(1<<i)<maxdepth;++i)
    for (j=1;j<=N;++j)
        {
         parinte[i+1][j]=parinte[i][parinte[i][j]];
         cmin[i+1][j]=(cmin[i][j]>cmin[i][parinte[i][j]]?cmin[i][j]:cmin[i][parinte[i][j]]);
        }
 for (j=1;j<=euler[0];++j)
     cmsc[0][j]=euler[j];
 for (i=0,pw=1;pw<euler[0];++i,pw<<=1)
     for (j=1;j+(pw<<1)-1<=euler[0];++j)
          if (nivel[cmsc[i][j]]<nivel[cmsc[i][j+pw]]) cmsc[i+1][j]=cmsc[i][j];
             else cmsc[i+1][j]=cmsc[i][j+pw];

}

int main()
{
 citire();
 dfs(radacina,1);
 stramosi();
 for (i=1;i<=M-P;++i)
     {
      if (X==Y) U=0;
	     else U=solve(X,Y);
      X=((X*A+Y*B)%N)+1;
      Y=((Y*C+U*D)%N)+1;
     }
 freopen("atac.out","w",stdout);
 for (i=M-P+1;i<=M;++i)
     {
      if (X==Y) U=0;
        else U=solve(X,Y);
      X=((X*A+Y*B)%N)+1;
      Y=((Y*C+U*D)%N)+1;
      printf("%d\n",U);
     }
 fclose(stdout);
 return 0;
}