Cod sursa(job #202294)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 7 august 2008 12:02:43
Problema Atac Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.65 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<<15
#define M_MAX 1<<15

typedef struct nod
{
	int x, c;
	nod *a;
} *pNod;
pNod v[32005];

//short int CM[N_MAX][1<<8],MA[N_MAX][1<<8];
int hg[N_MAX];
int CS[N_MAX],tata[N_MAX];
//short int stv[N_MAX],poz[N_MAX],lg[M_MAX],rmq[18][M_MAX];
//short int TA[18][N_MAX],drum[18][N_MAX];
int q,rez,s,f;
int maxhg,Z,X,Y,A,B,C,D,P,N,M;
bool viz[N_MAX];

void add(int x, int y, int c)
{
	pNod p;
	p = new nod;
	p -> x = y;
	p -> c = c;
	p -> a = v[x];
	v[x] = p;
}

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);
		add(i+1,x,y);
		add(x,i+1,y);
		//MA[ x ][ ++MA[x][0] ] = i+1;
		//MA[ i+1 ][ ++MA[i+1][0] ] = x;
		//CM[ x ][ ++CM[x][0] ] = y;
		//CM[ i+1 ][ ++CM[i+1][0] ] = y;
	}
	scanf("%d%d%d%d%d%d",&X,&Y,&A,&B,&C,&D);
}

void DF(int nod, int niv)
{
	viz[nod] = 1;
	pNod p;
	hg[nod] = niv;
	for (p = v[nod]; p != NULL; p = p -> a)
		if( !viz[p -> x] ) 
		{
			tata[p -> x] = nod;
			CS[p -> x] = p -> c;
			DF(p -> x, niv + 1);
		}
}

/*
void euler(int nod,int niv)
{
	//poz[nod] = stv[0] + 1;
	viz[nod] = true;
    hg[nod] = niv;  
	//if(hg[nod] > maxhg)
	//	maxhg = hg[nod];
    //stv[ ++stv[0] ] = nod;  
    FOR(i,1,MA[nod][0])  
		if(!viz[ MA[nod][i] ])
		{
			CS[ MA[nod][i] ] = CM[nod][i];
			tata[ MA[nod][i] ] = nod;
			euler(MA[nod][i],niv+1);  
			//stv[ ++stv[0] ] = nod;  
		} 
}
*/

void process()
{
   /*--lg[0];
	FOR(i,1,stv[0])
		lg[i] = lg[i/2] + 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];
		
	for(int i=1; (1<<i) <= maxhg;++i)
		for(int j=1; j <= N  ;++j)
			TA[i][j] = TA[i-1][ TA[i-1][j] ];
			
	FOR(i,1,N)
		drum[0][i] = CS[i];
	
	for(int i=1; (1<<i) <= maxhg;++i)
		for(int j=1; j <= N  ;++j)
			drum[i][j] = min(drum[i-1][j],drum[i-1][ TA[i-1][j] ]);
*/			
}

/*
int query(int nod1,int nod2)
{
	int x = poz[nod1],y = poz[nod2];
	if(x > y)
		swap(x,y);
	int dif = y-x+1;
	int log = lg[dif];
	if(hg[ rmq[log][x] ] < hg[ rmq[log][ y-(1<<log) + 1 ] ])
		return rmq[log][x];
	else
		return rmq[log][ y-(1<<log) + 1 ];
}
*/
/*
int querry_m(int x,int y)
{
	if(hg[y] >= hg[x])
		return 1<<20;
	int log = lg[ hg[x]-hg[y] ];
	return min(drum[log][x],querry_m(TA[log][x],y) );
}
*/

int find(int x, int y)
{
	int minim = 1<<30;
	if( hg[x] > hg[y])
	while( hg[x] != hg[y])
	{
		minim = min(minim,CS[x]);
		x = tata[x];
	}
	else 
		if (hg[x] < hg[y])
			while (hg[x] != hg[y])
			{
				minim = min(minim,CS[y]);
				y = tata[y];
			}
	while (x != y)
	{
		minim = min(minim,CS[x]);
		minim = min(minim,CS[y]);
		x = tata[x]; y = tata[y];
	}
	return minim;

}

void solve()
{
	//int nod;
	FOR(i,1,M)
	{
		rez =  1<<30;
		rez = find(X,Y);
		if(X == Y)
			rez=0;
		
		//nod=X;
		//rez = min(rez,querry_m(X,q) );
		//nod=Y;
		//rez = min(rez,querry_m(Y,q) ); 	
				
		if(i > M-P)
			printf("%d\n", rez);
		//printf("intre %d si %d avem LCA : %d si alegem o strada %d\n",X,Y,q,rez);
		Z = rez;
		
		X = (X*A + Y*B) % N + 1;
		Y = (Y*C + Z*D) % N + 1;
	
	}
}

int main()
{
	scan();
	DF(1,1);
	//euler(1,1);
	//process();
	solve();
	return 0;
}