Cod sursa(job #80805)

Utilizator VmanDuta Vlad Vman Data 30 august 2007 01:48:06
Problema Atac Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.05 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[4*Nmax];
vector<int> g[Nmax];

void 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;
     }
}

void update(int nod,int st,int dr,int a)
{
 int m=((st+dr)>>1);
 if (nivel[cmsc[nod]]>nivel[a]) cmsc[nod]=a;
 if (st==dr) return;
 if (i<=m) update((nod<<1),st,m,a);
    else update((nod<<1)+1,m+1,dr,a);
}

int query(int nod,int st,int dr,int X,int Y)
{
 int m=((st+dr)>>1),s1=0,s2=0;
 if ((X<=st)&&(Y>=dr)) return cmsc[nod];
 if (X<=m) s1=query((nod<<1),st,m,X,Y);
 if (Y>m)  s2=query((nod<<1)+1,m+1,dr,X,Y);
 if (nivel[s1]<nivel[s2]) return s1;
    return s2;
}

int solve(int X,int Y)
{
 int s,p,minim;
 if (pozitie[X]<pozitie[Y]) s=query(1,1,euler[0],pozitie[X],pozitie[Y]);
    else s=query(1,1,euler[0],pozitie[Y],pozitie[X]);
 minim=infinit;
 p=logN;
// pw=(1<<(p-1));
 while (X != s)
       {
        /*while (pw>nivel[s]-nivel[X])
              {
              pw=(pw>>1);
              --p;
              }*/
        while ((1<<(p-1))>nivel[s]-nivel[X])
              --p;
        minim=(cmin[p][X]<minim?cmin[p][X]:minim);
        X=parinte[p][X];
       }
 p=logN;
// pw=(1<<(p-1));
 while (Y != s)
       {
        /*while (pw>nivel[s]-nivel[Y])
              {
              pw=(pw>>1);
              --p;
              }*/
        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=1,j,p=1;
 while (p<=maxdepth)
       {
        for (j=1;j<=N;++j)
            {
            parinte[i][j]=parinte[i-1][parinte[i-1][j]];
            cmin[i][j]=(cmin[i-1][j]>cmin[i-1][parinte[i-1][j]]?cmin[i-1][j]:cmin[i-1][parinte[i-1][j]]);
            }
        ++i;
        p<<=1;
       }
}

int main()
{
 citire();
 dfs(radacina,1);
 stramosi();
 nivel[0]=infinit;
 for (i=1;i<=euler[0];++i)
     update(1,1,euler[0],euler[i]);
 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;
}