Cod sursa(job #252440)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 4 februarie 2009 14:22:34
Problema Atac Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <stdio.h>
#include <bitset>
#define N 32672
#define INF 10000000
#define minim(a,b) ((a<b)?a:b)
using namespace std;
struct muchie{int x,y;}a[N];
int n,m,p,T,i,j,x,y,q,nivel=0,L;
int g[N],poz[N],lg[N+N+N],r[20][N],E[N+N+N],NIV[N+N+N];
bitset <N> mark;
muchie * v[N];
int X,Y,A,B,C,D,sol,nod,t[20][N],d[20][N],dif[N];

inline int pmin(int x,int y){
  if ( NIV[x] <= NIV[y] )return x;
  else return y;
}

int RMQ(int x,int y){
  int D=y-x+1;  
  return pmin( r[ lg[D] ] [x], r[ lg[D] ] [ y -( 1 << lg[D] ) + 1 ] );
}

void DFS(int x){
  int i,fiu;
  mark[x]=1;
  ++nivel;
  E[++q]=x; NIV[q] = nivel;
  for (i=0;i<g[x];++i){
    fiu=v[x][i].x;
    if (!mark[fiu]){DFS(fiu);t[0][fiu]=x;d[0][fiu]=v[x][i].y; E[++q]=x; NIV[q] = nivel; }
  }
  nivel--;
}

int main(){
  freopen("atac.in","r",stdin); freopen("atac.out","w",stdout);
	scanf("%d %d %d",&n,&m,&p);
	for (i=2;i<=n;++i) {scanf("%d %d",&a[i].x,&a[i].y);g[i]++;g[a[i].x]++;}
	scanf("%d %d %d %d %d %d",&X,&Y,&A,&B,&C,&D);
	for (i=1;i<=n;++i)v[i]=(muchie*)malloc(g[i]*sizeof(muchie)),g[i]=0;
	for (i=2;i<=n;++i){
		 v[i][g[i]++]=a[i];
		 v[a[i].x][g[a[i].x]  ].x=i;
		 v[a[i].x][g[a[i].x]++].y=a[i].y;
	}
	
	//parcurgerea Euler
  DFS(1);
  for (i=1;i<=q;++i) if ( !poz[ E[i] ] ) poz[E[i]]=i;
	for (i=1;i<=q;++i) if ( !dif[ E[i] ] ) dif[E[i]]=NIV[i];

  //preproc
  for (i=1;i<=q;++i) r[0][i]=i;   //initializare pt 2^0
  for (i=2;i<=q;++i) lg[i] = lg[i>>1]+1;//vector de logaritmi
  L=lg[q];//cea mai mare putere a lui 2 mai mica decat n

  for ( j=q; j; j-- )
    for (i=1 ; i<=L && j+(1<<i) <= q+1 ; i++)
            r[i][j] = pmin( r[i-1][j], r[i-1][j+(1<<(i-1))] );

  //calculare stramosi
		L=lg[n];
		for (i=1;i<=L;++i)
    for (j=1;j<=n;++j){
      t[i][j]=t[i-1][t[i-1][j]];
			d[i][j]=minim(d[i-1][j],d[i-1][t[i-1][j]]);
		}
		
  //query
	T=m-p+1;
  for (i=1; i<=m; i++){
		x=X;y=Y;
		if (poz[x]>poz[y]){j=x;x=y;y=j;}
    nod = E[ RMQ(poz[x], poz[y]) ];
		sol=INF;
		
    x=X;
		y=dif[X]-dif[nod];
		L=lg[y];
		
    while (y>0){
			 if (d[L][x]<sol)sol=d[L][x];
       x=t[L][x];
			 y-=(1<<L);
       L=lg[y];
    }
		x=Y;y=dif[Y]-dif[nod];
		L=lg[y];
    while (y>0){
			 if (d[L][x]<sol)sol=d[L][x];
       x=t[L][x];
			 y-=(1<<L);
       L=lg[y];
    }
		if (X==Y)sol=0;
    if (i>=T) printf("%d\n",sol);
		X=(X*A+Y*B)%n+1;
		Y=(Y*C+sol*D)%n+1;
  }
	
return 0;
}