Cod sursa(job #221633)

Utilizator raduzerRadu Zernoveanu raduzer Data 17 noiembrie 2008 11:16:22
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include <cstdio>
#include <vector>
using namespace std;

const int MAX_N = 32010;
const int MAX_L = 16;

int n, m, p;
vector <int> f[MAX_N], cost[MAX_N];
int par[MAX_N][MAX_L], pret[MAX_N][MAX_L], lvl[MAX_N], fol[MAX_N];

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

void df(int x)
{
	int i, j, nod, l = f[x].size();
	
	for (j = 1, nod = par[x][0]; nod; nod = par[x][j - 1], ++j)
		if (par[x][j - 1]) 
		{
			par[x][j] = par[nod][j - 1];
			pret[x][j] = min(pret[x][j - 1], pret[nod][j - 1]);
		}
		
	for (i = 0; i < l; ++i)
	{
		nod = f[x][i];
		
		if (!fol[nod])
		{
			par[nod][0] = x;
			pret[nod][0] = cost[x][i];
			lvl[nod] = lvl[x] + 1;
			
			fol[x] = 1;
			df(nod);
			fol[x] = 0;
		}
	}
}

int LCA(int x, int y)
{
	int ret = 0x3f3f3f3f, i, bit;
	
	if (lvl[x] < lvl[y]) x ^= y ^= x ^= y;
	
	int val = lvl[x] - lvl[y];
	for (i = MAX_L - 1, bit = 1 << (MAX_L -1); i >= 0; --i, bit >>= 1)
		if (val & bit) 
		{
			ret = min(ret, pret[x][i]);
			x = par[x][i];
		}
	
	for (i = MAX_L - 1; i >= 0; --i)
		if (par[x][i] != par[y][i])
		{
			ret = min(ret, pret[x][i]);
			x = par[x][i];
			
			ret = min(ret, pret[y][i]);
			y = par[y][i];
		}
	
	if (x != y) ret = min(ret, min(pret[x][0], pret[y][0])); 
	
	return ret;
}

int main()
{
	int i, X, Y, m1, m2, m3, m4, x, y, c, Z;
	freopen("atac.in", "r", stdin);
	freopen("atac.out", "w", stdout);
	
	scanf("%d %d %d", &n, &m, &p);
	
	for (i = 2; i <= n; ++i)
	{
		scanf("%d %d", &x, &c);
		
		f[x].push_back(i);
		cost[x].push_back(c);
		
		f[i].push_back(x);
		cost[i].push_back(x);
	}
	
	lvl[1] = 1;
	df(1);
	
	scanf("%d %d %d %d %d %d", &X, &Y, &m1, &m2, &m3, &m4);
	
	for (i = 1; i <= m; ++i)
	{
		if (X == Y) Z = 0;
		else Z = LCA(X, Y);
		
		if (i > m - p) printf("%d\n", Z);
		
		X = (m1 * X + m2 * Y) % n + 1;
		Y = (m3 * Y + m4 * Z) % n + 1;
	}
}