Cod sursa(job #215631)

Utilizator stinkyStinky si Grasa stinky Data 19 octombrie 2008 19:37:31
Problema Atac Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include<stdio.h>

#define N 1<<15
#define L 15
#define MAX 100005

int n,m,p,tata[N],cost[N],stra[N][L],bom[N][L],nivel[N],a,b,c,d,x,y;

void citire()
{
	scanf("%d%d%d",&n,&m,&p);
	for(int i=2;i<=n;++i)
	{
		scanf("%d%d",&tata[i],&cost[i]);
		nivel[i]=1+nivel[tata[i]];
	}
	scanf("%d%d%d%d%d%d",&x,&y,&a,&b,&c,&d);
}

inline int minim(int a,int b)
{
	return a < b ? a : b;
}

void stramosi()//completeaza stra[i][j]=stramosul de 2^j al lui i si bom[i][j] costul min pt a distruge dr de la i la stra[i][j]
{
	for(int i=1;i<=n;++i)
	{
		stra[i][0]=tata[i];
		bom[i][0]=cost[i];
	}
	for(int i=1;i<=n;++i)
		for(int j=1;j<L;++j)
			if(stra[i][j-1] && stra[stra[i][j-1]][j-1])
			{
				stra[i][j]=stra[stra[i][j-1]][j-1];
				bom[i][j]=minim(bom[i][j-1],bom[stra[i][j-1]][j-1]);
			}
}

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

int lca(int p,int q)
{
	if(nivel[p]<nivel[q])
		schimb(p,q);
	int log=1,min=MAX;
	while((1<<log)<=nivel[p])//calculez log=[log(nivel[p])]
		++log;
	--log;
	//il aduc pe p pe acelasi nivel cu q
	for(int j=log; j>=0 && nivel[p]!=nivel[q] ; --j)
		if(nivel[p]-(1<<j)>=nivel[q])
		{
			min=minim(min,bom[p][j]);
			p=stra[p][j];
		}
	if(p==q)
		return min;
	//gasesc lca pt p si q
	for(int j=log ; j>=0 ; --j)
		if(nivel[p]>=(1<<j) && stra[p][j]!=stra[q][j])
		{
			min=minim(min,bom[p][j]);
			p=stra[p][j];
			min=minim(min,bom[q][j]);
			q=stra[q][j];
		}
	min=minim(min,bom[p][0]);
	min=minim(min,bom[q][0]);
	return min;
}

void calcul()
{
	int z;
	for(int i=1;i<=m;++i)
	{
		z=lca(x,y);
		if(i+p-1>=m)
			printf("%d\n",z);
		x = (x*a + y*b) % n + 1;
		y = (y*c + z*d) % n + 1;
	}
}


int main()
{
	freopen("atac.in","r",stdin);
	freopen("atac.out","w",stdout);
	citire();
	stramosi();
	//proba(stra);
	//proba(bom);
	calcul();
	return 0;
}