Cod sursa(job #2351809)

Utilizator flibiaVisanu Cristian flibia Data 22 februarie 2019 18:35:52
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, m, p, x, c, rmq[20][64100], mn[20][32100], st[64100], viz[32100], niv[32100], vf, dp[20][32100], pos[32100], cost[32100], dad[32100];
int X, Y, A, B, C, D, toto;
vector <int> v[32100], sol;

void dfs(int x, int lvl) {
	viz[x] = 1;
	st[++vf] = x;
	pos[x] = vf;
	niv[x] = lvl;
	for (auto y : v[x])
		if (!viz[y]) {
			dfs(y, lvl + 1);
			st[++vf] = x;
		}
}

void build() {
	for (int i = 1; i <= vf; i++)
		rmq[0][i] = st[i];
	int sz = log2(vf);
	for (int i = 1; i <= sz; i++)
		for (int j = 1; j <= vf; j++)
			rmq[i][j] = (niv[rmq[i - 1][j]] < niv[rmq[i - 1][j + (1 << (i - 1))]] ? rmq[i - 1][j] : rmq[i - 1][j + (1 << (i - 1))]);
}

void build2() {
	for (int i = 1; i <= n; i++)
		mn[0][i] = cost[i], dp[0][i] = dad[i];
	for (int i = 1; i <= 16; i++)
		for (int j = 1; j <= n; j++)
			mn[i][j] = min(mn[i - 1][j], mn[i - 1][dp[i - 1][j]]);
	for (int i = 1; i <= 16; i++)
		for (int j = 1; j <= n; j++)
			dp[i][j] = dp[i - 1][dp[i - 1][j]];
}

void solve(int x, int y) {
	int xx = x, yy = y;
	x = pos[x];
	y = pos[y];
	if (x > y)
		swap(x, y);
	int sz = log2(y - x + 1);
	int p = (niv[rmq[sz][x]] < niv[rmq[sz][y - (1 << sz) + 1]] ? rmq[sz][x] : rmq[sz][y - (1 << sz) + 1]);
	toto = INT_MAX;
	int d = niv[xx] - niv[p];
	for (int i = 0; i <= 16; i++)
		if (d & (1 << i)) {
			toto = min(toto, mn[i][xx]);
			xx = dp[i][xx];
		}
	d = niv[yy] - niv[p];
	for (int i = 0; i <= 16; i++)
		if (d & (1 << i)) {
			toto = min(toto, mn[i][yy]);
			yy = dp[i][yy];
		}
	if (toto == INT_MAX)
		toto = 0;
} 

int main() {
	in >> n >> m >> p;
	for (int i = 2; i <= n; i++) {
		in >> x >> c;
		v[x].push_back(i);
		cost[i] = c;
		dad[i] = x;
	}
	dfs(1, 1);
	build();
	build2();
	in >> X >> Y >> A >> B >> C >> D;
	for (int i = 1; i <= m; i++) {
		solve(X, Y);
		int xp, yp;
		xp = (X * A + Y * B) % n + 1LL;
		yp = (Y * C + toto * D) % n + 1LL;
		X = xp;
		Y = yp;
		if (i > m - p)
			sol.push_back(toto);
	}
	for (auto i : sol)
		out << i << '\n';
	return 0;
}