Cod sursa(job #233590)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 18 decembrie 2008 13:30:33
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <stdio.h>

int n, m, p, x, y, a, b, c, d, viz[32005];

int nivel[32005], cc[15][32005], minim[15][32005], rez;

typedef struct nod
{
	int x, c;
	nod *a;
} *pNod;
pNod v[32005];

inline int min(int x, int y){ return x < y ? x : y; }

void add(int x, int y, int c)
{
	pNod p;
	p = new nod;
	p -> x = y;
	p -> c = c;
	p -> a = v[x];
	v[x] = p;
}

void DF(int nod, int niv)
{
	viz[nod] = -1;
	pNod p;
	nivel[nod] = niv;
	for (p = v[nod]; p != NULL; p = p -> a)
		if (viz[p -> x] != -1) 
		{
			cc[0][p -> x] = nod;
			minim[0][p -> x] = p -> c;
			DF(p -> x, niv + 1);
		}
}

int aduc_pe_nivel(int y, int x)
{
	int i;
	i = 15;
	if (nivel[x] == y) return x;

	while (nivel[x] < (1<<i)) i--;
	while ((nivel[x] - (1<<i)) > y) i--;
	i--;

	rez = min(rez, minim[i][x]);
	x = cc[i][x]; 

	if (nivel[x] != y) return aduc_pe_nivel(y, x);
	else return x;
}

int LCA(int x, int y)
{
	rez = (1<<30);
	x = aduc_pe_nivel(min(nivel[x], nivel[y]), x);
	y = aduc_pe_nivel(min(nivel[x], nivel[y]), y);

	if (x == y) return x;

	int p, u, m;
	p = 0; u = nivel[x];

	while (p <= u)
	{
		m = (p + u) / 2;
		if (cc[m][x] != cc[m][y])
		{
			rez = min(rez, minim[m][x]);
			rez = min(rez, minim[m][y]);
			x = cc[m][x]; y = cc[m][y];
			p = m + 1;
		}
		else u = m - 1;		
	}
	if (m == 0)
	{
		rez = min(rez, minim[m][x]);
		rez = min(rez, minim[m][y]);
		x = cc[m][x], y = cc[m][y];
	}

	return x;
}

int main()
{
	freopen("atac.in","r",stdin);
	freopen("atac.out","w",stdout);

	int i, xn, yn, z, k, j;


	scanf("%d %d %d",&n,&m,&p);

	for (i = 1; i < n; i++)
	{
		scanf("%d %d",&x,&y);
		add(i+1,x,y);
		add(x,i+1,y);
	}

	scanf("%d %d %d %d %d %d",&x,&y,&a,&b,&c,&d);

	DF(1,1);
	for (k = 1; (1<<k) <= n; k++)
		for (i = 1; i <= n; i++)
		{
			cc[k][i] = cc[k - 1][cc[k - 1][i]];
			minim[k][i] = minim[k - 1][ minim[k - 1][i] ];
			for (j = 1; j <= k; j++) minim[k][i] = min(minim[j - 1][ minim[j - 1][i] ], minim[k][i]);
		}

	for (i = 1; i <= m; i++)
	{
		if (x == y) z = 0;
		else z = LCA(x, y);

		xn = (x * a + y * b) % n + 1;
		yn = (y * c + rez * d) % n + 1;

		if (i > m - p) printf("%d\n",rez);
		x = xn, y = yn;
	}

	return 0;
}