Cod sursa(job #476896)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 12 august 2010 16:21:07
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <stdio.h>
#include <vector>
#define Nmax 32002
#define pb push_back
#define mp make_pair
#define Ct 19
#define INF 2147000000

using namespace std;

vector< pair<int,int> > v[Nmax];
int Niv[Nmax];
int Str[Ct][Nmax],Min[Ct][Nmax];
int n,m,P,nmax,Z;

inline int Minim(int x,int y){ return x<y ? x:y; }
inline int Maxim(int x,int y){ return x>y ? x:y; }

inline void dfs(int x,int niv){
	vector< pair<int,int> >::iterator it;
	Niv[x]=niv; 
	if( niv> nmax ) nmax=niv;
	
	for(it=v[x].begin(); it!=v[x].end(); ++it)
		if( ! Niv[it->first] ){
			Str[0][it->first]=x;
			Min[0][it->first]=it->second;
			dfs(it->first,niv+1);
		}
}

inline void afla(int x,int y){
	int px,py,p,aux;
	if( Niv[x] < Niv[y] ) aux=x, x=y, y=aux;
	for(px=0; (1<<px) <= Niv[x]; ++px); --px;
	for(py=0; (1<<py) <= Niv[y]; ++py); --py;
	
	for(p=px; p>=0; --p)
		if( Niv[x]-(1<<p) >= Niv[y] )
			Z=Minim(Z,Min[p][x]),x=Str[p][x];
	
	for(p=py; p>=0; --p)
		if( Str[p][x] != Str[p][y] ){
			Z=Minim(Z,Min[p][x]); x=Str[p][x]; 
			Z=Minim(Z,Min[p][y]); y=Str[p][y]; 
		}
	if( x != y ){
		Z=Minim(Z,Min[0][x]);
		Z=Minim(Z,Min[0][y]);
	}
}

int main(){
	int X,Y,A,B,C,D,i,j,x,y,p;
	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",&x,&y);
		v[i].pb(mp(x,y));
		v[x].pb(mp(i,y));
	}
	scanf("%d%d%d%d%d%d",&X,&Y,&A,&B,&C,&D);
	
	dfs(1,1); --nmax;
	for(p=0; (1<<p)<=nmax; ) ++p; --p;
	for(i=1;i<=p;++i)
		for(j=1;j<=n;++j){
			Str[i][j]=Str[i-1][Str[i-1][j]];
			Min[i][j]=Minim(Min[i-1][Str[i-1][j]], Min[i-1][j]);
		}
	
	for(i=1;i<=m;++i){
		Z=INF;
		if( X==Y ) Z=0;
		else afla(X,Y);
		
		if( i>= m-P+1 )printf("%d\n",Z);
		
		X=( X*A + Y*B ) % n +1;
		Y=( Y*C + Z*D ) % n +1;
		//scanf("%d%d",&X,&Y);
	}
	
	fclose(stdin); fclose(stdout);
	return 0;
}