Cod sursa(job #419516)

Utilizator mihaionlyMihai Jiplea mihaionly Data 17 martie 2010 17:32:22
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 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 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;
 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;
 for(graf *g=G[nod];g!=NULL;g=g->urm)
  {
  dfs(g->x,l+1);
  Eu[++k]=nod;
  lv[k]=l;
  }
 }
void rmq()
 {
 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))]);
 }
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 fc(int s,int st)
 {
 int min=oo;
 while(s!=st)
  {
  if(min>Cs[s])
   min=Cs[s];
  s=Tt[s];
  }
 return min;
 }
int main()
 {
 int i,lca;
 read();
 dfs(1,0);
 rmq();
 for(i=1;i<=m;i++)
  {
  lca=query(min(Pa[X],Pa[Y]),max(Pa[X],Pa[Y]));
  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;
 }