Cod sursa(job #3354491)

Utilizator Alexutu008Ionita Alexandru-Dumitru Alexutu008 Data 18 mai 2026 17:08:20
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <bits/stdc++.h>

using namespace std;

const int N = 32001, E = 16;

int anc[E][N], mn[E][N]; // stramosul/minimul de la j urcat cu 2**e nivele
int lvl[N], lg[N];
int n, m, p;
int x, y, a, b, c, d, z = 1e9;
vector<pair<int, int>> mc[N];

void dfs(int nod) {
	for (auto& i : mc[nod]) {
		lvl[i.first] = lvl[nod] + 1;
		dfs(i.first);
	}
}

int get_anc(int nod, int ord) {
	for (int bit = 0; (1 << bit) <= ord; ++bit) {
		if ((1 << bit) & ord) {
			nod = anc[bit][nod];
		}
	}

	return nod;
}

int get_min(int nod, int ord) {
	int minimum = 1e9;

	for (int bit = 0; (1 << bit) <= ord; ++bit) {
		if ((1 << bit) & ord) {
			minimum = min(minimum, mn[bit][nod]);
			nod = anc[bit][nod];
		}
	}

	return minimum;
}

void lca(int x, int y, int& z) {
	int ord = lg[lvl[x]];

	while (ord >= 0) {
		if (anc[ord][x] != anc[ord][y]) {
			z = min(z, min(mn[ord][x], mn[ord][y]));
			x = anc[ord][x];
			y = anc[ord][y];
		}
		--ord;
	}

	z = min(z, min(mn[0][x], mn[0][y]));

	if (m < p)
		cout << z << '\n';
}

int main() {
	freopen("atac.in", "r", stdin);
	freopen("atac.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m >> p;
	for (int i = 2; i <= n; ++i) {
		int nod, cost;
		cin >> nod >> cost;
		mc[nod].push_back({ i, cost });
		  
		anc[0][i] = nod;
		mn[0][i] = cost;
	}
	cin >> x >> y >> a >> b >> c >> d;

	for (int i = 2; i < N; ++i) lg[i] = lg[i / 2] + 1;

	int rad = anc[0][1];
	if (rad == 0) rad = 1;
	while (anc[0][rad]) rad = anc[0][rad];

	dfs(rad);

	for (int e = 1; e < E; ++e) {
		for (int i = 1; i <= n; ++i) {
			anc[e][i] = anc[e - 1][anc[e - 1][i]];
			mn[e][i] = min(mn[e - 1][i], mn[e - 1][anc[e - 1][i]]);
		}
	}

	while (m--) {
		if (x == y) {
			z = 0;
		}
		else if (lvl[x] < lvl[y]) {
			z = get_min(y, lvl[y] - lvl[x]);
			y = get_anc(y, lvl[y] - lvl[x]);
		}
		else if (lvl[y] < lvl[x]) {
			z = get_min(x, lvl[x] - lvl[y]);
			x = get_anc(x, lvl[x] - lvl[y]);
		}

		if (x == y) {
			if (m < p)
				cout << z << '\n';
		}
		else {
			lca(x, y, z);
		}

		x = (x * a + y * b) % n + 1;
		y = (y * c + z * d) % n + 1;
		z = 1e9;
	}

	return 0;
}