Cod sursa(job #419850)

Utilizator mihaionlyMihai Jiplea mihaionly Data 18 martie 2010 08:21:58
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <cstdio>
using namespace std;
FILE *f=fopen("atac.in","r");
FILE *g=fopen("atac.out","w");
#define nmax 32005
#define oo 100005
struct graf
 {
 int x,c;
 graf *urm;
 };
graf *G[nmax];
int X,Y,A,B,C,D,Z;
int n,m,p;
int log2[nmax];
int Eu[nmax*4],lv[nmax*4],k;
int Pa[nmax];
int RMQ[20][nmax*4];
int stm[20][nmax*4],cst[20][nmax*4],lmax;
int Tt[nmax],Cs[nmax];
inline int min(int x,int y)
 {
 if(x<y) 
  return x;
 return y;
 }
inline int max(int x,int y)
 {
 if(x>y)
  return x;
 return y;
 }
inline int minl(int l1,int l2)
 {
 if(lv[l1]<lv[l2])
  return l1;
 return l2;
 }
void add(graf *&g,int x,int c)
 {
 graf *p=new graf;
 p->x=x;
 p->c=c;
 p->urm=g;
 g=p;
 }
void read()
 {
 fscanf(f,"%d %d %d",&n,&m,&p);
 int i,u,v;
 Cs[0]=oo;
 for(i=2;i<=n;i++)
  {
  fscanf(f,"%d %d",&u,&v);
  add(G[u],i,v);
  Tt[i]=u;
  Cs[i]=v;
  //add(G[i],u,v);
  }
 fscanf(f,"%d %d %d %d %d %d",&X,&Y,&A,&B,&C,&D);
 fclose(f);
 }
void dfs(int nod,int l)
 {
 Eu[++k]=nod;
 lv[k]=l;
 if(!Pa[nod])
  Pa[nod]=k;
 if(l>lmax)
  lmax=l;
 for(graf *g=G[nod];g!=NULL;g=g->urm)
  {
  dfs(g->x,l+1);
  Eu[++k]=nod;
  lv[k]=l;
  }
 }
void build()
 {
 int i,j;
 RMQ[0][1]=1;
 for(i=2;i<=k;i++) {log2[i]=log2[i/2]+1;RMQ[0][i]=i;}
 for(i=1;(1<<i)<=k;i++)
  for(j=1;j+(1<<i)-1<=k;j++)
   RMQ[i][j]=minl(RMQ[i-1][j],RMQ[i-1][j+(1<<(i-1))]);
 for(i=2;i<=n;i++)
  {
  stm[0][i]=Tt[i];
  cst[0][i]=Cs[i];
  }
 cst[0][0]=cst[0][1]=oo;
 Cs[0]=Cs[1]=oo;
 for(i=1;(1<<i)<=lmax;i++)
  {
  cst[i][0]=cst[i][1]=oo;
  for(j=2;j<=n;j++)
   {
   stm[i][j]=stm[i-1][stm[i-1][j]];
   cst[i][j]=min(cst[i-1][j],cst[i-1][stm[i-1][j]]);
   }
  }
 }
int query(int x,int y)
 {
 int dif,k;
 dif=y-x+1;
 k=log2[dif];
 if(lv[RMQ[k][x]]<lv[RMQ[k][y-(1<<k)+1]])
  return Eu[RMQ[k][x]];
 return Eu[RMQ[k][y-(1<<k)+1]];
 }
int stramosi(int p,int q)
 {
 int j;
 while(q&&p)
  {
  for(j=log2[lmax];j>=0&&p&&q;j--)
   {
   if((1<<j)<=q&&p&&q)
    {
    p=stm[j][p];
	q-=(1<<j);
    }
   }
  }
 return p;
 }
int fc(int st,int s)
 {
 if(s==st) return oo;
 int dif,l;
 dif=lv[Pa[st]]-lv[Pa[s]];
 l=log2[dif];
 return min(cst[l][st],cst[l][stramosi(st,dif-1-l)]);
 }
int main()
 {
 int i,lca;
 read();
 dfs(1,0);
 build();
 for(i=1;i<=m;i++)
  {
  lca=query(min(Pa[X],Pa[Y]),max(Pa[X],Pa[Y]));
  if(X==Y) Z=0;
  else Z=min(fc(X,lca),fc(Y,lca));
  X=(X*A+Y*B)%n+1;
  Y=(Y*C+Z*D)%n+1;
  if(i>=m-p+1)
   fprintf(g,"%d\n",Z);
  }
 return 0;
 }