Cod sursa(job #391262)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 5 februarie 2010 13:21:10
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 kb
#include<cstdio>
#define N 32001
#include<vector>
#define minim(a,b) ((a<b)?(a):(b))
#define pb push_back
#define OO 1<<30
using namespace std;
vector<int>g[N],dep(N,0);
int a[18][N],c[18][N],str;
int n,m,p,x,y,a1,b,c1,d,z,z1,dim,jum,log[N],pr[N],ad[18][N<<2],e[18][N<<2];
void df(int x)//reprezentarea euler
{
	e[0][++e[0][0]]=x;
	ad[0][e[0][0]]=dep[x];
	if (!pr[x])
		pr[x]=e[0][0];
	size_t g1=g[x].size();
	for (size_t i=0; i<g1; ++i)
	{
		if (dep[g[x][i]]) continue;
		dep[g[x][i]]=1+dep[x];
		df(g[x][i]);
		e[0][++e[0][0]]=x;
		ad[0][e[0][0]]=dep[x];
	}
}
void calcul_stramos()
{
	int p=pr[x],u=pr[y],lo;
	if (p>u)
		swap(p,u);
	if (p==u)
		str=x;
	else
	{
		dim=1<<log[u-p+1];
		lo=log[u-p+1];
		if(ad[lo][p]<ad[lo][u-dim+1])
			str=e[lo][p];
		else
			str=e[lo][u-dim+1];
	}
}
void calcul_z()
{
	int p=dep[x]-dep[str];
	z1=x;
	int putere=0;
	while (p)
	{
		if (p&1)
		{
			z=minim(z,c[putere][z1]);
			z1=a[putere][z1];
		}
		++putere;
		p>>=1;
	}
	putere=0;
	p=dep[y]-dep[str];
	z1=y;
	while (p)
	{
		if (p&1)
		{
			z=minim(z,c[putere][z1]);
			z1=a[putere][z1];
		}
		++putere;
		p>>=1;
	}
}
void afis(int a[18][N])
{
	for (int i=1; i<=log[n]; ++i)
	{
		for (int j=1; j<=n; ++j)
			printf("%d ",a[i][j]);
		printf("\n");
	}
	printf("\n");
}
void afis1(int a[18][N*5])
{
	for (int i=0; i<=log[e[0][0]]; ++i)
	{
		for (int j=1; j<=e[0][0]; ++j)
			printf("%d ",a[i][j]);
		printf("\n");
	}
	printf("\n");
}
void citire()
{
	freopen("atac.in","r",stdin);
	freopen("atac.out","w",stdout);
	scanf("%d%d%d",&n,&m,&p);
	for (int i=2; i<=n; ++i)
	{
		scanf("%d%d",&a[0][i],&c[0][i]);
		g[a[0][i]].pb(i);
		//g[i].pb(x);
	}
	c[0][1]=c[0][0]=OO;
	log[2]=1;
	for (int i=3; i<=n; ++i)
		log[i]=log[i>>1]+1;
	for (int i=1; i<=log[n]; ++i)//calculez stramosii si costurile minime
	{
		c[i][1]=c[i][0]=OO;
		for (int j=1; j<=n; ++j)
		{
			a[i][j]=a[i-1][a[i-1][j]];
			c[i][j]=minim(c[i-1][j],c[i-1][a[i-1][j]]);
		}
	}
	//afis(a);
	//afis(c);
	dep[1]=1;
	df(1);
	for (int i=n+1; i<=e[0][0]; ++i)
		log[i]=log[i>>1]+1;
	for (int i=1; i<=log[e[0][0]]; ++i)
	{
		dim=1<<i;
		jum=dim>>1;
		for (int j=1; j+dim-1<=e[0][0]; ++j)
		{
			if (ad[i-1][j]<ad[i-1][j+jum])
			{
				ad[i][j]=ad[i-1][j];
				e[i][j]=e[i-1][j];
			}
			else
			{
				ad[i][j]=ad[i-1][j+jum];
				e[i][j]=e[i-1][j+jum];
			}
		}
	}
	//afis1(ad);
	//afis1(e);
	scanf("%d%d%d%d%d%d",&x,&y,&a1,&b,&c1,&d);
	//calculez al px si py-lea stramos
	calcul_stramos();
	z=OO;
	calcul_z();
	for (int i=1; i<=m; ++i)
	{
		x=(x*a1+y*b)%n+1;
		y=(y*c1+z*d)%n+1;
		z=OO;
		calcul_stramos();
		calcul_z();
		if (m-p+1<=i)
			printf("%d\n",z);
	}
}
int main()
{
	citire();
	return 0;
}