Cod sursa(job #202241)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 7 august 2008 01:05:32
Problema Atac Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <stdio.h>

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

int nivel[32005], t[32005];

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

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) 
		{
			t[p -> x] = nod;
			cost[p -> x] = p -> c;
			DF(p -> x, niv + 1);
		}
}




int find(int x, int y)
{
	int minim = 200000;
	if (nivel[x] > nivel[y])
		while (nivel[x] != nivel[y])
		{
			minim = min(minim,cost[x]);
			x = t[x];
		}
	else 
	if (nivel[x] < nivel[y])
		while (nivel[x] != nivel[y])
		{
			minim = min(minim,cost[y]);
			y = t[y];
		}

	while (x != y)
	{
		minim = min(minim,cost[x]);
		minim = min(minim,cost[y]);
		x = t[x]; y = t[y];
	}
	return minim;
			
}

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

	int i, xn, yn, z;

	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 (i = 1; i <= m; i++)
	{
		if (x == y) z = 0;
		else z = find(x, y);

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

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

	return 0;
}