Cod sursa(job #57558)

Utilizator scapryConstantin Berzan scapry Data 2 mai 2007 16:24:29
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.94 kb
#include <stdio.h>
#include <algorithm>

/*
 * LCA in  < O(N*logN), O(1) >  and queries in O(logN)
 */

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

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

int n;
int dad[maxn];
int cost[maxn];
int euler[maxn * 2];
int depth[maxn * 2];
int pos[maxn]; //pos[i] = some position of i in euler[]
int now_pos, now_depth;
int best[logmaxn][maxn * 2]; //best[j][i] = position of minimum in depth[i, i + 2^j - 1]
int fbit[maxn * 2];
int grandpa[logmaxn][maxn]; //grandpa[j][i] = node which is 2^j up from i
int ans[logmaxn][maxn]; //ans[j][i] = position of minimum in cost[ i, grand[j][i] ]

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

void do_euler(int node)
{
	euler[now_pos] = node;
	depth[now_pos] = now_depth;

	pos[node] = now_pos; //first occurrence

	now_pos++;
	now_depth++;

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

		euler[now_pos] = node;
		depth[now_pos] = now_depth - 1;
		now_pos++;
	}

	now_depth--;
}

void calc_best()
{
	int i, j;

	for(i = 0; i < 2 * n - 1; i++)
		best[0][i] = i;

	for(i = 1; (1 << i) < 2 * n - 1; i++)
	{
		for(j = 0; j + (1 << i) - 1 < 2 * n - 1; j++)
		{
			best[i][j] = best[i - 1][j];

			if(depth[ best[i][j] ] > depth[ best[i - 1][ j + (1 << (i - 1)) ] ])
				best[i][j] = best[i - 1][ j + (1 << (i - 1)) ];
		}
	}
}

void calc_fbit()
{
	fbit[0] = -1; //don't use this!

	int bit = 0, i;

	for(i = 1; i < 2 * n - 1; i++)
	{
		if(i >= (1 << bit))
		{
			bit++;
		}

		fbit[i] = bit - 1;
	}
}

void calc_grandpa()
{
	int i, j;

	for(j = 0; j < n; j++)
		grandpa[0][j] = dad[j];

	for(i = 1; i < logmaxn; i++)
	{
		for(j = 0; j < n; j++)
			grandpa[i][j] = grandpa[i - 1][ grandpa[i - 1][j] ];
	}
}

void calc_ans()
{
	int i, j;

	for(j = 0; j < n; j++)
		ans[0][j] = j;

	for(i = 1; (1 << i) < n; i++)
	{
		for(j = 0; j < n; j++)
		{
			ans[i][j] = ans[i - 1][j];

			if(cost[ ans[i][j] ] > cost[ ans[i - 1][ grandpa[i - 1][j] ] ])
				ans[i][j] = ans[i - 1][ grandpa[i - 1][j] ];
		}
	}
}

inline void precalc()
{
	do_euler(0);
	calc_best();
	calc_fbit();
	calc_grandpa();
	calc_ans();
}

int rmq(int a, int b)
//a, b are positions in euler[], returns position in euler[]
{
	int l = fbit[b - a]; //the offset
	int a2 = b - (1 << l) + 1;

	if(depth[ best[l][a] ] < depth[ best[l][a2] ])
		return best[l][a];
	else
		return best[l][a2];
}

int lca(int a, int b)
//a and b are nodes, returns a node
{
	if(a == b) //rmq() can't handle this (fbit[0] == -1 and shit)
		return euler[ pos[a] ];

	if(pos[a] > pos[b])
	{
		int tmp = a;
		a = b;
		b = tmp;
	}

	int r = rmq(pos[a], pos[b]);
	return euler[r];
}

int get_ans(int node, int up)
//"up" nodes from "node" - returns node with minimum cost
{
	int start = node;
	int bit = fbit[up];
	int ret = node;

	while(up)
	{
		if(cost[ ans[bit][start] ] < cost[ret])
			ret = ans[bit][start];

		//start += (1 << bit);
		start = grandpa[bit][start];
		up &= ~(1 << bit);
		bit = fbit[up];
	}

	return ret;
}

int calc(int a, int b)
{
	if(a == b) return 0; //free ride!

	int l = lca(a, b);
	int ra, rb;

	if(l == a)
		ra = 0; //so that cost[ra] == inf
	else
		ra = get_ans(a, depth[ pos[a] ] - depth[ pos[l] ]);

	if(l == b)
		rb = 0; //so that cost[ra] == inf
	else
		rb = get_ans(b, depth[ pos[b] ] - depth[ pos[l] ]);

	return std::min(cost[ra], cost[rb]);
}

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;

	cost[0] = inf;
	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;
}