Cod sursa(job #80731)

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

#define Nmax 32768
#define logN 17
#define radacina 0
#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,pw,diferenta=pozitie[Y]-pozitie[X];
 for (i=0,pw=1;(pw<<1)<=diferenta;++i,pw=(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,i,p,minim;
 if (pozitie[X]<pozitie[Y]) s=lca(X,Y);
    else s=lca(Y,X);
 i=X;
 minim=infinit;
 p=logN;
 while (i!=s)
       {
        while ((1<<(p-1))>nivel[s]-nivel[i])
              --p;
        if (cmin[p][i]<minim) minim=cmin[p][i];
        i=parinte[p][i];
       }
 i=Y;
 p=logN;
 while (i!=s)
       {
        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,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=(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];

}

void dfs(int p,int poz,int depth)
{
 int nod=g[p][poz],i;
 maxdepth=(depth>maxdepth?depth:maxdepth);
 parinte[0][nod]=p;
 cmin[0][nod]=cost[p][poz];
 nivel[nod]=depth++;
 euler[pozitie[nod]=(++euler[0])]=nod;
 poz=g[nod].size();
 for (i=0;i<poz;++i)
     if (nivel[g[nod][i]]==0)
        {
         dfs(nod,i,depth);
         euler[++euler[0]]=nod;
        }
}
/*
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();
 g[0].push_back(1);
 cost[0].push_back(0);
 dfs(radacina,0,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;
}