Cod sursa(job #650736)

Utilizator mlupseLupse-Turpan Mircea mlupse Data 18 decembrie 2011 20:47:47
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
using namespace std;
#include <cstdio>
#include <vector>
#define NMax 32010
#define INF 1<<30
#define min(a,b) ((a)>(b))?(b):(a);

int N, M, P, idx,MaxLevel;
int TT[20][NMax], CM[20][NMax], Level[NMax],Rmq[20][NMax<<1],Log2[NMax<<1];
int E[NMax<<1],First[NMax],Lev[NMax<<1];

vector <pair<int, int> > G[NMax];

inline void DFS(int nod)
{	
	E[++idx]=nod;
	Lev[idx]=Level[nod];
	First[nod]=idx;
	
	for (vector <pair<int, int> >::iterator it=G[nod].begin(); it!=G[nod].end(); it++) 
	{
		int v=it->first;
		if (TT[0][v]) continue;
		
		TT[0][v]=nod;
		Level[v]=Level[nod]+1;
		CM[0][v]=it->second;
		if (Level[v]>MaxLevel) MaxLevel=Level[v];
			DFS(v);
		E[++idx]=nod;
		Lev[idx]=Level[nod];
	}
}

inline void RMQ()
{
	int i, j;
	for (i=2; i<=idx; i++) Log2[i]=Log2[i>>1]+1;
	
	for (i=1; i<=idx; i++) Rmq[0][i]=i;
	for (i=1; (1<<i)<idx; i++)
		for (j=1; j<=idx-(1<<i)+1; j++)
			if (Lev[Rmq[i-1][j]]<Lev[Rmq[i-1][j+(1<<(i-1))]])
				Rmq[i][j]=Rmq[i-1][j]; else
					Rmq[i][j]=Rmq[i-1][j+(1<<(i-1))];
}

inline void swap(int &a,int &b)
{
int aux;
aux=a;
a=b;
b=aux;
}

inline int LCA(int x, int y)
{
	x=First[x];
	y=First[y];
	if (x>y) swap(x, y);
	int d=Log2[y-x+1];
	
	if (Lev[Rmq[d][x]]<Lev[Rmq[d][y-(1<<d)+1]])
		return E[Rmq[d][x]]; 
	else
		return E[Rmq[d][y-(1<<d)+1]];
}

inline int Search(int x, int y)
{
	if (x==y) return INF;
	int d=Log2[Level[x]-Level[y]];
	
	if (Level[TT[d][x]]==Level[y]) return CM[d][x]; 
	else
		return min(CM[d][x], Search(TT[d][x], y));
}
	
int main()
{
	freopen("atac.in","r",stdin);
	freopen("atac.out","w",stdout);
	
	int i,j,lca,X,Y,A,B,C,D,Z;
	
	scanf("%d %d %d", &N, &M, &P);
	
	for (i=2; i<=N; i++)
	{
		scanf("%d %d", &X, &Y);
		G[X].push_back(make_pair(i, Y));
		G[i].push_back(make_pair(X, Y));
	}
	
	Level[1]=1;
	DFS(1);
	
	for (i=1; (1<<i)<=MaxLevel; i++)
		for (j=1; j<=N; j++)
		{
			TT[i][j]=TT[i-1][TT[i-1][j]];
			if (TT[i][j]) CM[i][j]=min(CM[i-1][j],CM[i-1][TT[i-1][j]]);
		}
		
	RMQ();
	
	scanf("%d %d %d %d %d %d", &X, &Y, &A, &B, &C, &D);
	
	while (M--)
	{
		if (X==Y) 
			Z=0; 
		else
			{
			lca=LCA(X,Y);
			Z=min(Search(X,lca), Search(Y,lca));
			}
		
		if (M<P) printf("%d\n",Z);
		
		X=(X*A+Y*B)%N+1;
		Y=(Y*C+Z*D)%N+1;
	}
}