Cod sursa(job #201790)

Utilizator andrei-alphaAndrei-Bogdan Antonescu andrei-alpha Data 3 august 2008 20:46:56
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.24 kb
using namespace std;

#include <cstdio>
#include <algorithm>

#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<<19

short int MA[N_MAX][1<<13];
int hg[N_MAX];
int sol[M_MAX],tata[N_MAX];
short int CS[N_MAX],PV[19][N_MAX];
int q,rez,s,f,sef;
int Z,X,Y,A,B,C,D,P,N,M;
bool bo[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", &x,&y);
		tata[i+1] = x; 
		MA[ x ][ ++MA[x][0] ] = i+1;
		bo[i+1] = 1;
		CS[i+1] = y;
	}
	scanf("%d%d%d%d%d%d",&X,&Y,&A,&B,&C,&D);
	
	FOR(i,1,N)
		if(!bo[i])
		{
			sef=i;
			break;
		}	
}

void euler(int nod,int niv)
{
	hg[nod] = niv;
	FOR(i,1,MA[nod][0])
		euler(MA[nod][i],niv+1);
}

void process()
{
    for(int i = 0; i < N; ++i)
        for(int j = 0; 1 << j < N; ++j)
            PV[j][i] = -1;
  
    for(int i = 0; i < N; ++i)
        PV[0][i] = tata[i];
   
    for(int j = 1; 1 << j < N; ++j)
        for(int i = 0; i < N; ++i)
            if (PV[j - 1][i] != -1)
                PV[j][i] = PV[j-1][ PV[j - 1][i] ];
}
 

int query(int p, int q)
{
    int tmp, log, i;
    if (hg[p] < hg[q])
        tmp = p, p = q, q = tmp;
  
    for (log = 1; 1 << log <= hg[p]; ++log);
		log--;
    for (i = log; i >= 0; --i)
        if (hg[p] - (1 << i) >= hg[q])
            p = PV[i][p];
    if (p == q)
        return p;
    for (i = log; i >= 0; --i)
        if (PV[i][p] != -1 && PV[i][p] != PV[i][q])
            p = PV[i][p], q = PV[i][q];
   
    return tata[p];
}

  
void solve()
{
	int nod;
	FOR(i,1,M)
	{
		rez =  0;
		if(X == Y)
			goto exit_0;
		rez =  1<<20;
		q = query(X,Y);
		
		nod=X;
		while(nod != q)
		{
			if(rez > CS[nod] )
				rez = CS[nod];
			nod = tata[nod];
		}	
		
		nod=Y;
		while(nod != q)
		{
			if(rez > CS[nod] )
				rez = CS[nod];
			nod = tata[nod];
		}	
		
		exit_0:
		if(i > M-P)
			sol[ ++sol[0] ] = 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) + 1;
		Y = (Y*C + Z*D) % (N-1) + 1;
	
	}
	
	FOR(i,1,sol[0])
		printf("%d\n", sol[i]);
}

int main()
{
	scan();
	euler(sef,1);
	++N;
	process();
	solve();
	return 0;
}