Cod sursa(job #52988)

Utilizator scapryConstantin Berzan scapry Data 20 aprilie 2007 16:03:14
Problema Atac Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <assert.h>
#include <stdio.h>

/*
 * Naive LCA
 */

enum { maxn = 32001, inf = 0x3F3F3F3F };

struct ls
{
	int n;
	ls *next;
} *lst[maxn];

int n;
int dad[maxn];
int cost[maxn];
int lev[maxn];
bool v[maxn]; //not really needed
int depth;

void add(int from, int to)
{
	ls *p = new ls;
	p->n = to;
	p->next = lst[from];
	lst[from] = p;
}

void df(int node)
{
	assert(!v[node]);
	v[node] = true;
	lev[node] = depth;

	depth++;

	for(ls *p = lst[node]; p; p = p->next)
		df(p->n);

	depth--;
}

void precalc()
{
	df(0);
}

int lca(int a, int b)
{
	if(lev[a] > lev[b])
	{
		int t = a;
		a = b;
		b = t;
	}
	assert(lev[a] <= lev[b]);

	while(lev[a] != lev[b])
		b = dad[b];

	while(a != b)
	{
		assert(a != 0 && b != 0);
		assert(lev[a] = lev[b]);
		a = dad[a];
		b = dad[b];
	}

	return a;
}

int calc(int a, int b)
{
	int c = lca(a, b);
	int i, ret = inf;

	for(i = a; i != c; i = dad[i])
		if(cost[i] < ret) ret = cost[i];

	for(i = b; i != c; i = dad[i])
		if(cost[i] < ret) ret = cost[i];

	return ret;
}

int main()
{
	int i, count, interested, start_printing;
	int x, y, z, a, b, c, d;
	FILE *f = fopen("atac.in", "r");
	if(!f) return 1;

	fscanf(f, "%d%d%d", &n, &count, &interested);
	start_printing = count - interested;

	for(i = 1; i < n; i++)
	{
		fscanf(f, "%d%d", &dad[i], &cost[i]);
		dad[i]--;

		add(dad[i], i);
	}

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

	fclose(f);
	f = fopen("atac.out", "w");
	if(!f) return 1;

	precalc();

	for(i = 0; i < count; i++)
	{
		z = calc(x - 1, y - 1);

		if(i >= start_printing)
			fprintf(f, "%d\n", z);

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

	fclose(f);
	return 0;
}