Cod sursa(job #369771)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 29 noiembrie 2009 15:48:14
Problema Atac Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <stdio.h>
#include <vector>
#define N 1<<15
#define P 1<<16
#define inf 1000000000
#define pb push_back
#define mp make_pair
#define f first 
#define s second
using namespace std;
int n,m,qrys,r;
vector < pair<int,int> > v[N];
int ap[N],euler[P],grd[N],nivel[P],lg[P];
int rmq[20][P],p,q,a,b,c,d,mat[20][N],mat2[20][N];
char marc[N];
void read()
{
	scanf("%d%d%d",&n,&m,&qrys);
	int i,x,y;
	for (i=2; i<=n; i++)
	{
		scanf("%d%d",&x,&y);
		v[x].pb(mp(i,y));
		mat[0][i]=y;
		mat2[0][i]=x;
	}
	scanf("%d%d%d%d%d%d",&p,&q,&a,&b,&c,&d);
}
inline int min(int a,int b)
{
	if (grd[a]<grd[b])
		return a;
	return b;
}
inline int minim(int a,int b)
{
	return a<b ? a : b;
}
void dfs(int nod)
{
	int i;
	marc[nod]=1;
	for (i=0; i<v[nod].size(); i++)
		if (!marc[v[nod][i].f])
		{
			euler[++r]=v[nod][i].f;
			if (!ap[v[nod][i].f])
				ap[v[nod][i].f]=r;
			grd[v[nod][i].f]=grd[nod]+1;
			dfs(v[nod][i].f);
			euler[++r]=nod;
		}
}
void precalc()
{
	int i,j;
	for (i=1; (1<<i)<=n; i++)
		for (j=1; j<=n; j++)
		{
			mat[i][j]=minim(mat[i-1][j],mat[i-1][mat2[i-1][j]]);
			mat2[i][j]=mat2[i-1][mat2[i-1][j]];
		}
}
void make_rmq()
{
	int i,j,t,k;
	for (i=1; i<=r; i++)
	{
		lg[i]=i>=2 ? lg[i/2]+1 : 0;
		rmq[0][i]=euler[i];
	}
	for (i=1; (1<<i)<=r; i++)
	{
		t=1<<i;
		k=1<<(i-1);
		for (j=1; j<=r-t+1; j++)
			rmq[i][j]=min(rmq[i-1][j],rmq[i-1][(j+t-1)-k+1]);
	}
}
int calcul(int rez,int p)
{
	int nr=grd[p]-grd[rez];
	int i,sol=inf,indice=p;
	for (i=0; i<=15; i++)
		if (nr & (1<<i))
		{
			if (mat[i][indice])
				sol=minim(sol,mat[i][indice]);
			indice=mat2[i][indice];
		}
	return sol;
}
void queries()
{
	int i,x,y,z,t,l,rez,p1,q1;
	for (i=1; i<=m; i++)
	{
		x=ap[p];
		y=ap[q];
		if (x>y){
			t=x;  x=y;  y=t;
		}
		l=lg[y-x+1];
		t=1<<l;
		rez=min(rmq[l][x],rmq[l][y-t+1]);
		z=minim(calcul(rez,p),calcul(rez,q));
		if (i>=m-qrys+1)
			printf("%d\n",z);
		p1=(p*a+q*b)%n+1;
		q1=(q*c+z*d)%n+1;
		p=p1;
		q=q1;
	}
}
int main()
{
	freopen("atac.in","r",stdin);
	freopen("atac.out","w",stdout);
	read();
	euler[++r]=1;
	ap[1]=1;
	dfs(1);
	precalc();
	make_rmq();
	queries();
	return 0;
}