Cod sursa(job #712283)

Utilizator eudanipEugenie Daniel Posdarascu eudanip Data 13 martie 2012 11:38:21
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.24 kb
//http://9gag.com/gag/2993003
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

#define INF 1000000005
#define LMAX 16
#define pi pair<int,int>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define NMAX 33005

int rmq[NMAX][LMAX + 2],vmin;
int min_rmq[NMAX][LMAX + 2];
int px,py,a,b,c,d,n,m,p,rez;
int h[NMAX];

vector< pi > v[NMAX];
char viz[NMAX];

int find(int nod,int val,int put)
{
    	if(!val)
        	return nod;
    	if((1<<put) > val)
        	return find(nod, val, put - 1);
        	
        vmin = min(vmin, min_rmq[nod][put]);	
    	return find(rmq[nod][put],val - (1<<put), put - 1);
}

int lca(int nod1,int nod2)
{
    	int i;
    	vmin = INF; 
    	
    	if(h[nod1] > h[nod2])
        	nod1 = find(nod1, h[nod1] - h[nod2], LMAX);
    	else if(h[nod1] < h[nod2])
        	nod2 = find(nod2, h[nod2] - h[nod1], LMAX);
        	
    	for(i = LMAX; i >= 0; i--)
        	if(rmq[nod1][i] != rmq[nod2][i])
        	{
            		nod1 = rmq[nod1][i];
            		nod2 = rmq[nod2][i];
            		vmin = min(vmin, min_rmq[nod1][i]);
            		vmin = min(vmin, min_rmq[nod2][i]);
        	}
    	if(nod1 == nod2)
        	return vmin;
        
        vmin = min(vmin, min_rmq[nod1][0]);
        vmin = min(vmin, min_rmq[nod2][0]);
    	return vmin;
}


void read()
{
	scanf("%d%d%d", &n, &m, &p);
	
	for(int i = 1; i < n; i++)	
	{
		scanf("%d%d", &a, &b);
		v[a].pb(mp(i + 1, b));
		v[i + 1].pb(mp(a, b));
	}	
	
	scanf("%d%d%d%d%d%d", &px, &py, &a, &b, &c, &d);
}

void dfs(int nod)
{
	viz[nod] = 1;
	int i,vec,lim = v[nod].size();	
	
	for(i = 1; i < LMAX; i++)
	{
		rmq[nod][i] = rmq[rmq[nod][i - 1]][i - 1];
		min_rmq[nod][i] = min(min_rmq[nod][i - 1], min_rmq[rmq[nod][i - 1]][i - 1]);
	}
	
	for(i = 0; i < lim; i++)
		if(!viz[vec = v[nod][i].x])
		{
			h[vec] = h[nod] + 1;
			rmq[vec][0] = nod;
			min_rmq[vec][0] = v[nod][i].y;
			dfs(vec);
		}
}

int main ()
{
	int i,xp,yp;
	
	freopen("atac.in","r",stdin);
	freopen("atac.out","w",stdout);
	
	read();
	dfs(1);	
	for(i = 1; i <= m; i++)
	{
		if(px == py)
			rez = 0;
		else
			rez = lca(px, py);
		if(i >= m - p + 1)		
			printf("%d\n",rez);
				
		xp = (px * a + py * b) % n + 1;
		yp = (py * c + rez * d) % n + 1;
		px = xp;
		py = yp;
	}
		
	
	return 0;
}