Cod sursa(job #202366)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 7 august 2008 19:54:37
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.44 kb
using namespace std;

#include <cstdio>
#include <algorithm>
#include <vector>

#define IN "atac.in"
#define OUT "atac.out"

#define min(x,y) x < y ? x : y
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define N_MAX 1<<16
#define M_MAX 1<<18
#define pb push_back
#define vi vector< vector<int> >

int hg[N_MAX];
int CS[N_MAX],tata[N_MAX];
int stv[M_MAX],poz[N_MAX],lg[M_MAX];
int rmq[18][M_MAX],TA[18][N_MAX];
int drum[18][N_MAX];
int best,q,rez,s,f;
int maxhg,Z,X,Y,A,B,C,D,P,N,M;
vi AM(N_MAX),CM(N_MAX);

void scan()
{
	int x,y;
	freopen(IN, "r",stdin);
	freopen(OUT, "w",stdout);
	scanf("%d%d%d\n", &N,&M,&P);
	
	FOR(i,1,N-1)
	{
		scanf("%d%d\n", &x,&y);
		AM[x].pb(i+1);
		AM[i+1].pb(x);
		CM[x].pb(y);
		CM[i+1].pb(y);
	}
	scanf("%d%d%d%d%d%d",&X,&Y,&A,&B,&C,&D);
}

void euler(int nod, int niv)
{
	stv[ ++stv[0] ] = nod; 
	poz[nod] = stv[0];
	hg[nod] = niv;
	maxhg = max(maxhg,niv);
	
	int l = AM[nod].size();
	for(int i=0; i<l ;++i)
		if ( !poz[ AM[nod][i] ] ) 
		{
			tata[ AM[nod][i] ] = nod;
			CS[ AM[nod][i] ] = CM[nod][i];
			euler( AM[nod][i] , niv + 1);
			stv[ ++stv[0] ] = nod; 
		}
}

void process()
{
   --lg[0];
	FOR(i,1,stv[0])
		lg[i] = lg[i>>1] + 1;
	
	FOR(i,1,stv[0])
		rmq[0][i] = stv[i];
		
	for(int i=1; (1<<i) <= stv[0];++i)
		for(int j=1;j+(1<<i)-1 <= stv[0];++j)
			if(hg[ rmq[i-1][j] ] < hg[ rmq[i-1][ j+(1<<i) - (1<<(i-1))] ])
				rmq[i][j] = rmq[i-1][j];
			else
				rmq[i][j] = rmq[i-1][j+(1<<i) - (1<<(i-1))];
	FOR(i,1,N)
		TA[0][i] = tata[i],
		drum[0][i] = CS[i];
		
	for(int i=1; (1<<i) <= maxhg;++i)
		for(int j=1; j <= N  ;++j)
		{
			if(hg[j] < 1<<i )
				continue;
			TA[i][j] = TA[i-1][ TA[i-1][j] ],
			drum[i][j] = min(drum[i-1][j],drum[i-1][ TA[i-1][j] ]);
		}	
}


inline int LCA(int nod1,int nod2)
{
	int x = poz[nod1],y = poz[nod2];
	if(x > y)
		swap(x,y);
	int log = lg[y-x+1];
	if(hg[ rmq[log][x] ] < hg[ rmq[log][ y-(1<<log) + 1 ] ])
		return rmq[log][x];
	else
		return rmq[log][ y-(1<<log) + 1 ];
}


void query(int x,int y)
{
	if(hg[y] < hg[x])
	{
		int log = lg[ hg[x]-hg[y] ];
		if(rez > drum[log][x] )
			rez = drum[log][x];
		query(TA[log][x],y);
	}	
}

void solve()
{
	int nod;
	FOR(i,1,M)
	{
		if(X == Y)
			rez=0;
		else
		{
			rez = 1<<30;
			nod = LCA(X,Y);
			query(X,nod);
			query(Y,nod);
		}	
		if(i > M-P)
			printf("%d\n", rez);
		Z = rez;
		
		X = (X*A + Y*B) % N + 1;
		Y = (Y*C + Z*D) % N + 1;
	
	}
}

int main()
{
	scan();
	euler(1,1);
	vi ().swap(AM);
	vi ().swap(CM);
	process();
	solve();
	return 0;
}