Cod sursa(job #88977)

Utilizator stef2nStefan Istrate stef2n Data 5 octombrie 2007 02:39:53
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 kb
//#define DEBUG

#include <cstdio>
#include <vector>
#ifdef DEBUG
#include <iostream>
#endif
using namespace std;

#define NMAX 32005
#define LOGMAX 16
#define INF 100000000

int N,M,P,X,Y,Z,A,B,C,D;
vector < pair<int,int> > lista[NMAX];
int F[LOGMAX][NMAX],MIN[LOGMAX][NMAX],level[NMAX];

void read_data()
{
	int u,inf;
	scanf("%d %d %d",&N,&M,&P);
	for(int i=2; i<=N; i++)
	{
		scanf("%d %d",&u,&inf);
		lista[u].push_back(make_pair(i,inf));
		lista[i].push_back(make_pair(u,inf));
	}
	scanf("%d %d %d %d %d %d",&X,&Y,&A,&B,&C,&D);
}

void DF(int node, int father)
{
	for(vector < pair<int,int> > :: iterator it = lista[node].begin(); it != lista[node].end(); ++it)
		if(it->first != father)
		{
			F[0][it->first]=node;
			MIN[0][it->first]=it->second;
			level[it->first]=level[node]+1;
			DF(it->first,node);
		}
}

void init()
{
	F[0][1]=-1;
	MIN[0][1]=INF;
	level[1]=0;
	DF(1,-1);
	for(int i=1; i<LOGMAX; i++)
		for(int j=1; j<=N; j++)
		{
			F[i][j] = F[i-1][j]==-1 ? -1 : F[i-1][F[i-1][j]];
			MIN[i][j] = F[i-1][j]==-1 ? MIN[i-1][j] : min(MIN[i-1][j],MIN[i-1][F[i-1][j]]);
		}
}

int previous(int x, int step)
{
	int jump=0;
	while(step)
	{
		if(step&1)
			x=F[jump][x];
		jump++;
		step>>=1;
	}
	return x;
}

int min_from_path(int x, int step)
{
	int jump=0,sol=INF;
	while(step)
	{
		if(step&1)
		{
			sol=min(sol,MIN[jump][x]);
			x=F[jump][x];
		}
		jump++;
		step>>=1;
	}
	return sol;
}

int LCA(int x, int y)
{
	if(x==y)
		return INF;
	int sol=INF;
	for(int k=LOGMAX-1; k>=0; k--)
		if(F[k][x]!=F[k][y])
		{
			sol=min(sol,MIN[k][x]);
			sol=min(sol,MIN[k][y]);
			x=F[k][x];
			y=F[k][y];
		}
	if(F[0][x]==F[0][y])
	{
		sol=min(sol,MIN[0][x]);
		sol=min(sol,MIN[0][y]);
	}
	return sol;
}

int solve(int x, int y)
{
	if(x==y)
		return 0;
	int sol=INF;
	if(level[x]<level[y])
	{
		sol=min(sol,min_from_path(y,level[y]-level[x]));
		y=previous(y,level[y]-level[x]);
	}
	if(level[x]>level[y])
	{
		sol=min(sol,min_from_path(x,level[x]-level[y]));
		x=previous(x,level[x]-level[y]);
	}
	sol=min(sol,LCA(x,y));
	return sol;
}


int main()
{
	freopen("atac.in","r",stdin);
	freopen("atac.out","w",stdout);
	read_data();
	init();
#ifdef DEBUG
	cerr<<"Niveluri in arbore:"<<endl;
	for(int i=1; i<=N; i++)
		cerr<<level[i]<<" ";
	cerr<<endl;

	cerr<<"Parinti:"<<endl;
	for(int i=1; i<=N; i++)
		cerr<<F[0][i]<<"("<<MIN[0][i]<<") ";
	cerr<<endl;

	cerr<<"Bunici:"<<endl;
	for(int i=1; i<=N; i++)
		cerr<<F[1][i]<<"("<<MIN[1][i]<<") ";
	cerr<<endl;

	cerr<<"Strabunici:"<<endl;
	for(int i=1; i<=N; i++)
		cerr<<F[2][i]<<"("<<MIN[2][i]<<") ";
	cerr<<endl;

	cerr<<"Interogari:"<<endl;
#endif
	for(int i=1; i<=M; i++)
	{
		Z=solve(X,Y);
#ifdef DEBUG
		cerr<<"\tDe la "<<X<<" la "<<Y<<": "<<Z<<endl;
#endif
		if(i>=M-P+1)
			printf("%d\n",Z);
		X = ((long long)X*(long long)A + (long long)Y*(long long)B) % (long long)N + 1;
		Y = ((long long)Y*(long long)C + (long long)Z*(long long)D) % (long long)N + 1;
	}
	return 0;
}