Cod sursa(job #547928)

Utilizator jeanFMI - Petcu Ion Cristian jean Data 6 martie 2011 20:26:45
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.52 kb
#include<stdio.h>
#include<vector>
#define Nmax 32010
#define Inf 100010
using namespace std ;

int H[Nmax<<1], Rmq[20][Nmax<<1], E[Nmax<<1], Min[20][Nmax], first[Nmax], Lg[Nmax<<1], Str[20][Nmax], sol[Nmax>>1];
int n,m,p,P,x,y,a,b,c,d,M1,M2,i,vsd,T ; 
vector<int> Arb[Nmax]; 

void dfs ( int nod, int h ) 
{
	E[++vsd] = nod ; 
	H[vsd] = h ; 
	first[nod] = vsd ;
	
	int i, N = Arb[nod].size() ; 
	
	for( i = 0 ; i < N ; i++ )
	{
		dfs( Arb[nod][i], h+1 ) ; 
		E[++vsd] = nod ; 
		H[vsd] = h ;
	}
}

void rmq() 
{
	int i,k,L;
	
	L = Lg[vsd];

	for( i = 1 ; i <= vsd ; i++ )
		Rmq[0][i] = i ; 
	
	for( k = 1 ; k <= L ; k++ )
		for( i = 1 ; i + (1<<k) - 1 <= vsd ; i++ )
			if( H[ Rmq[k-1][i] ] <= H[ Rmq[k-1][i+(1<<(k-1))] ] ) 
				Rmq[i][k] = Rmq[k-1][i];
			else
				Rmq[i][k] = Rmq[k-1][i+(1<<(k-1))] ; 
}

int lca ( int x, int y ) 
{
	x = first[x] ;
	y = first[y] ; 
	if( x > y ) { int aux = x ; x = y ; y = aux ; }
	
	int L = Lg[y-x+1], rez;

	if( H[ Rmq[L][x] ] <= H[ Rmq[L][y-(1<<L)+1] ] ) 
		rez = Rmq[L][x] ;
	else
		rez = Rmq[L][y-(1<<L)+1] ; 
	
	return E[rez];
}

void precalc()
{
	int i,k, nn = n<<1, L, lvl  ; 
	
	for( i = 2 ; i <= nn ; i++ )
		Lg[i] = 1 + Lg[i>>1] ;
	
	L = Lg[n];
	
	for( k = 1 ; k <= L ; k++ )
		for( i = 1 ; i <= n  ; i++ )
			Str[k][i] = Str[k-1][Str[k-1][i]];
	
	for( k = 1 ; k <= L ; k++ )
		for( i = 1 ; i <= n ; i++ )
		{
			lvl = H[ first[i] ] ; 
			if( lvl == 0 ) continue ; 
			if( Lg[lvl] + 1 < k ) continue ; 
			
			if( Min[k-1][i] <= Min[k-1][Str[k-1][i]] ) 
				Min[k][i] = Min[k-1][i] ; 
			else
				Min[k][i] = Min[k-1][Str[k-1][i]] ; 
		}
}

int query ( int nod, int tata )
{
	int rez = Inf, L ;
	int n1 = H[first[nod]], n2 = H[first[tata]];
	
	while( n1 != n2 ) 
	{
		L = Lg[n1-n2] ; 
		if( Min[L][nod] < rez ) rez = Min[L][nod] ; 
		n1 -= (1<<L);
		nod = Str[L][nod];
	}
	
	return rez ; 
}
	
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",&Str[0][i],&Min[0][i]) ;
		Arb[Str[0][i]].push_back(i);
	}
	
	dfs(1,0);
	rmq();
	precalc();
	
	scanf("%d %d %d %d %d %d",&x,&y,&a,&b,&c,&d);
	
	for( i = 1 ; i <= m ; i++ )
	{
		T = lca(x,y);
		M1 = query(x,T);
		M2 = query(y,T);
		
		if( M1 > M2 ) M1 = M2 ; P++;
		
		if( P >= p ) sol[P-p+1] = M1 ; 
		
	    x = (x*a + y*b) % n + 1 ; 
		y = (y*c + M1*d) % n + 1 ; 
	}
	
	for( i = 1 ; i <= p ; i++ )
		printf("%d\n",sol[i]);
	
	return 0 ; 
}