Cod sursa(job #78162)

Utilizator VmanDuta Vlad Vman Data 15 august 2007 18:53:44
Problema Atac Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.75 kb
#include <stdio.h>
#include <vector>
using namespace std;

#define Nmax 32768
#define logN 17
#define radacina 1
#define infinit 1000000

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],cost[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);
     g[U].push_back(i);
     g[i].push_back(U);
     cost[U].push_back(V);
     cost[i].push_back(V);
     }
 scanf("%d %d %d %d %d %d",&X,&Y,&A,&B,&C,&D);
 fclose(stdin);
}

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

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

void stramosi()
{
 int i,j;
 for (i=1;(1<<i)<=maxdepth;++i)
    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]]);
        }
 for (j=1;j<=euler[0];++j)
     cmsc[0][j]=euler[j];
 for (i=1;(1<<i)<=euler[0];++i)
     for (j=1;j+(1<<i)-1<=euler[0];++j)
          if (nivel[cmsc[i-1][j]]<nivel[cmsc[i-1][j+(1<<(i-1))]]) cmsc[i][j]=cmsc[i-1][j];
             else cmsc[i][j]=cmsc[i-1][j+(1<<(i-1))];

}

void dfs(int nod,int p,int minim,int depth)
{
 int i;
 maxdepth=(depth>maxdepth?depth:maxdepth);
 //informatiile nodului
 nivel[nod]=depth;
 parinte[0][nod]=p;
 cmin[0][nod]=minim;
 euler[++euler[0]]=nod;
 pozitie[nod]=euler[0];
 //parcurg in adancime
 ++depth;
 for (i=0;i<g[nod].size();++i)
     if (nivel[g[nod][i]]==0)
       {
        dfs(g[nod][i],nod,cost[nod][i],depth);
     	euler[++euler[0]]=nod;
       }
}

int main()
{
 citire();
 dfs(radacina,0,0,1);
 stramosi();
 for (i=1;i<=M-P;++i)
     {
      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)
     {
      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;
}