Cod sursa(job #1384889)

Utilizator vladrochianVlad Rochian vladrochian Data 11 martie 2015 15:06:11
Problema Atac Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <fstream>
#include <vector>
using namespace std;

typedef pair<int, int> Pair;
const int kMaxN = 32005, kMaxLog = 16, kInf = 0x3f3f3f3f;

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

int N, M, P, X, Y, A, B, C, D;
vector<Pair> G[kMaxN];
bool use[kMaxN];
int lg2[kMaxN << 1];
Pair anc[kMaxLog][kMaxN];
int level[kMaxN], rmq[kMaxLog][kMaxN << 1], euler_crt, first[kMaxN];

void DFS(int node) {
	use[node] = true;
	rmq[0][++euler_crt] = node;
	first[node] = euler_crt;
	for (auto it : G[node])
		if (!use[it.first]) {
			level[it.first] = level[node] + 1;
			anc[0][it.first] = Pair(node, it.second);
			DFS(it.first);
			rmq[0][++euler_crt] = node;
		}
}

inline int MinLevel(int a, int b) {
	return level[a] < level[b] ? a : b;
}

int LCA(int x, int y) {
	x = first[x];
	y = first[y];
	if (x > y)
		swap(x, y);
	int lg = lg2[y - x];
	return MinLevel(rmq[lg][x], rmq[lg][y - (1 << lg) + 1]);
}

int MinEdge(int node, int ancestor) {
	int dif = level[node] - level[ancestor], ans = kInf;
	for (int step = 0; step < kMaxLog; ++step)
		if (dif & (1 << step)) {
			ans = min(ans, anc[step][node].second);
			node = anc[step][node].first;
		}
	return ans;
}

int main() {
	fin >> N >> M >> P;
	for (int i = 2; i <= N; ++i) {
		int u, v;
		fin >> u >> v;
		G[i].emplace_back(u, v);
		G[u].emplace_back(i, v);
	}
	fin >> X >> Y >> A >> B >> C >> D;
	level[1] = 1;
	DFS(1);
	for (int i = 2; i < (kMaxN << 1); ++i)
		lg2[i] = lg2[i >> 1] + 1;
	for (int i = 1; i < kMaxLog; ++i) {
		for (int j = 1; j <= N; ++j) {
			anc[i][j].first = anc[i - 1][anc[i - 1][j].first].first;
			anc[i][j].second = min(anc[i - 1][j].second, anc[i - 1][anc[i - 1][j].first].second);
		}
		for (int j = 1; j <= euler_crt - (1 << i) + 1; ++j)
			rmq[i][j] = MinLevel(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]);
	}
	while (M--) {
		int lca = LCA(X, Y);
		int ans = (X == Y) ? 0 : min(MinEdge(X, lca), MinEdge(Y, lca));
		if (M < P)
			fout << ans << "\n";
		X = (X * A + Y * B) % N + 1;
		Y = (Y * C + ans * D) % N + 1;
	}
	return 0;
}