Cod sursa(job #974866)

Utilizator tudorv96Tudor Varan tudorv96 Data 18 iulie 2013 16:18:00
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <fstream>
#include <vector>
#include <list>
using namespace std;

#define pb push_back
#define last (int)(E.size()-1)

vector <list <int> > g;
vector <vector <int> > rmq, t, dmin;
vector <int> tata, F, E, L, v, bp;
int n, m, X, Y, A, B, C, D, p;

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

int cmp(int a, int b) {
	return ((L[a] < L[b]) ? a : b);
}

void Resize() {
	g.resize(n+1);
	tata.resize(n+1);
	E.reserve(2*n+10);
	L.reserve(2*n+10);
	F.resize(n+1);
	v.resize(n+1);
}

void dfs (int x, int val) {
	E.pb(x);
	L.pb(val);
	F[x] = last;
	for (list <int> :: iterator it = g[x].begin(); it != g[x].end(); ++it) {
		dfs(*it, val + 1);
		E.pb(x);
		L.pb(val);
	}
}

void RMQ() {
	bp.resize(last+1);
	for (int i = 2; i <= last; ++i)
		bp[i] = bp[i/2] + 1;
	rmq.resize(bp[last] + 1);
	dmin.resize(bp[n] + 1);
	t.resize(bp[n] + 1);
	for (int i = 0; i <= bp[last]; ++i) {
		if (i <= bp[n]) {
			t[i].resize(n+1);
			dmin[i].resize(n+1);
		}
		rmq[i].resize(last+1);
	}
	for (int i = 1; i <= last; ++i) {
		if (i <= n) {
			t[0][i] = tata[i];
			dmin[0][i] = v[i];
		}
		rmq[0][i] = i;
	}
	for (int i = 1; i <= bp[last]; ++i)
		for (int j = 1; j <= last - (1 << i) + 1; ++j)
			rmq[i][j] = cmp(rmq[i-1][j], rmq[i-1][j + (1 << (i - 1))]);
	for (int i = 1; i <= bp[n]; ++i)
		for (int j = 1; j <= n; ++j) {
				t[i][j] = t[i-1][t[i-1][j]];
				dmin[i][j] = min (dmin[i-1][j], dmin[i-1][t[i-1][j]]);
		}
}

int query(int x, int y) {
	int dif = L[F[x]] - L[F[y]], res = 0x3f3f3f3f; 
	for (int i = 0; i <= bp[dif]; ++i)
		if ((1 << i) & dif) {
			res = min (res, dmin[i][x]);
			x = t[i][x];
		}
	return res;
}
int LCA(int x, int y) {
	int a = F[x], b = F[y];
	if (a > b)
		swap (a, b);
	int pow = bp[b - a + 1]; 
	return E[cmp(rmq[pow][a], rmq[pow][b + 1 - (1 << pow)])];
}			
		
int main() {
	fin >> n >> m >> p;
	Resize();
	for (int i = 2; i <= n; ++i) {
		fin >> tata[i] >> v[i];
		g[tata[i]].pb (i);
	}
	fin >> X >> Y >> A >> B >> C >> D;
	E.pb(0);
	L.pb(0);
	dfs(1, 0);
	RMQ();
	while (m--) {
		int lca = LCA(X, Y), Z = 0x3f3f3f3f;
		if (X != Y) {
			Z = min (Z, query (X, lca));
			Z = min (Z, query (Y, lca));
		}
		else
			Z = 0;
		if (m < p)
			fout << Z << "\n";
		X = (X * A + Y * B) % n + 1;
		Y = (Y * C + Z * D) % n + 1;
	}
}