Cod sursa(job #476871)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 12 august 2010 15:39:05
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <stdio.h>
#include <vector>
#define Nmax 32002
#define pb push_back
#define mp make_pair
#define Ct 19
#define Emax Nmax*5
#define INF 2147000000

using namespace std;

vector< pair<int,int> > v[Nmax];
int E[Emax],poze[Emax];
int Rmq[Ct][Emax];
int Niv[Nmax],use[Nmax];
int Str[Ct][Nmax],Min[Ct][Nmax];
int n,m,P,nmax;

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

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);
		}
}

void euler(int x){
	vector< pair<int,int> >:: iterator it;
	
	E[++E[0]]=x;
	poze[x]=E[0];
	
	for(it=v[x].begin(); it!=v[x].end(); ++it)
		if( ! poze[it->first] ){
			euler(it->first);
			E[++E[0]]=x;
		}
}

void rmq(){
	int i,j,pmax=0;
	while( (1<<pmax) <= E[0] ) ++pmax;
	--pmax; if(pmax<0) pmax=0;
	
	for(i=1;i<=E[0];++i) Rmq[0][i]=Niv[E[i]];
	for(i=1; i<=pmax; ++i)
		for(j=1; j+(1<<i)-1<=E[0]; ++j)
			Rmq[i][j]=Minim( Rmq[i-1][j] , Rmq[i-1][j+(1<<(i-1))] );
}

inline int afla_lca(int x,int y){
	int p=0;
	while( x+(1<<p) <=y ) ++p;
	--p; if(p<0) p=0;
	
	return Minim(Rmq[p][x],Rmq[p][y-(1<<p)+1]);
}

inline int afla_str(int x, int y){
	int rez=INF,i=0;
	while( y ){
		while( (1<<i) <= y ) ++i;
		--i; if(i<0) i=0;
		
		y-=(1<<i);
		rez=Minim(rez,Min[i][x]);
		x=Str[i][x];
	}
	return rez;
}

int main(){
	int X,Y,Z,A,B,C,D,niv_lca,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]);
		}
	
	euler(1); 
	rmq();
	
	for(i=1;i<=m;++i){
		niv_lca = afla_lca(Minim(poze[X],poze[Y]), Maxim(poze[X],poze[Y]));
		Z = Minim( afla_str(X,Niv[X]-niv_lca), afla_str(Y,Niv[Y]-niv_lca) );
		
		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;
}