Cod sursa(job #369311)

Utilizator Mishu91Andrei Misarca Mishu91 Data 27 noiembrie 2009 22:04:14
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <fstream>
#include <vector>

using namespace std;

#define MAX_N 32005
#define MAX_L 20
#define MAX_P 10005
#define INF 0x3f3f3f3f

#define nod first
#define cst second
#define foreach(V) for(typeof (V).begin() it = (V).begin(); it != (V).end(); ++it)

ifstream fin ("atac.in");
ofstream fout ("atac.out");

int N, M, P, T[MAX_L][MAX_N], D[MAX_L][MAX_N], L[MAX_N], Sol[MAX_P];
int X, Y, A, B, C, R;
vector <pair<int, int> > G[MAX_N]; 

void citire()
{
	fin >> N >> M >> P;

	for(int i = 2; i <= N; ++i)
	{
		int x, c;
		fin >> x >> c;
		G[x].push_back(make_pair(i, c));
		G[i].push_back(make_pair(x, c));
	}

	fin >> X >> Y >> A >> B >> C >> R;
}

void dfs(int nod, int ant, int lev)
{
	L[nod] = lev;

	foreach(G[nod])
	{
		int act = it -> nod, cst = it -> cst;
		if(act == ant) continue;
		T[0][act] = nod;
		D[0][act] = cst;
		dfs(act, nod, lev+1);
	}
}

void pre()
{
	for(int k = 1; (1 << k) < N; ++k)
		for(int i = 1; i <= N; ++i)
		{
			T[k][i] = T[k-1][T[k-1][i]];
			D[k][i] = min(D[k-1][i], D[k-1][T[k-1][i]]);
		}
}

int lca(int x, int y)
{
	if(L[x] < L[y])
		swap(x, y);

	int log1, log2;
	for(log1 = 1; (1 << log1) < L[x]; ++log1);
	for(log2 = 1; (1 << log2) < L[y]; ++log2);

	for(int k = log1; k >= 0; --k)
		if(L[x] - (1 << k) >= L[y])
			x = T[k][x];

	if(x == y) return x;

	for(int k = log2; k >= 0; --k)
		if(T[k][x] != T[k][y])
			x = T[k][x], 
			y = T[k][y];

	return T[0][x];
}

int dist(int x, int y)
{
	int sol(INF), log(1);
	for(; (1 << log) < L[x]; ++log);

	for(int k = log; k >= 0; --k)
		if(L[x] - (1 << k) >= L[y])
			sol = min(sol, D[k][x]),
			x = T[k][x];

	return sol;
}

void solve()
{
	int Z(0);
	for(int i = 1; i <= M; ++i)
	{
		int l = lca(X, Y);
		
		if(X == Y)
			Z = 0;
		else	
			Z = min(dist(X, l), dist(Y, l));

//		printf("%d %d %d\n", X, Y, Z);
		
		if(i > M-P)
			Sol[i-M+P] = Z;
		X = ((X*A + Y*B) % N) + 1;
		Y = ((Y*C + Z*R) % N) + 1;
	}

	for(int i = 1; i <= P; ++i)
		fout << Sol[i] << "\n";
}

int main()
{
	citire();
	dfs(1, 0, 0);
	pre();
	solve();
}