Cod sursa(job #2446474)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 9 august 2019 02:25:56
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <bits/stdc++.h>

using namespace std;

const int NMax = 32050;
const int LMax = 16;

int lvl[NMax];
pair < int, int > lift[LMax][NMax];
vector < vector < pair < int, int > > > G;

void DFS(int node, int father, int cost) {
	for (auto x : G[node]) {
		if (x.first == father) continue;
		lvl[x.first] = lvl[node] + 1;
		DFS(x.first, node, x.second);
	}
	lift[0][node] = {father, cost};
}

int lca(int x, int y) {
	if (x == y || x == 0 || y == 0) return 0;
	if (lvl[x] < lvl[y]) {
		swap(x, y);
	}

	int logx, logy;
	for (logx = 1; (1 << logx) < lvl[x]; ++logx);
	for (logy = 1; (1 << logy) < lvl[y]; ++logy);

	int mn = INT_MAX;
	for (int i = logx; i >= 0; --i) {
		if (lvl[x] - (1 << i) >= lvl[y]) {
			mn = min(mn, lift[i][x].second);
			x = lift[i][x].first;
		}
	}

	if (x == y) return mn;

	for (int i = logy; i >= 0; --i) {
		if (lift[i][x].first != 0 && lift[i][x].first != lift[i][y].first) {
			mn = min(mn, lift[i][x].second);
			mn = min(mn, lift[i][y].second);
			x = lift[i][x].first;
			y = lift[i][y].first;
		}
	}

	return min({mn, lift[0][x].second, lift[0][y].second});
}

int main() {
	ifstream cin("atac.in");
	ofstream cout("atac.out");

	int n, m, p;
	cin >> n >> m >> p;

	G.assign(n + 5, {});
	for (int i = 2; i <= n; ++i) {
		int u, v;
		cin >> u >> v;

		G[u].push_back({i, v});
		G[i].push_back({u, v});
	}

	DFS(1, 0, 0);
	for (int i = 1; i < LMax; ++i) {
		for (int j = 1; j <= n; ++j) {
			pair < int, int > next = lift[i - 1][lift[i - 1][j].first];
			lift[i][j] = {next.first, min(lift[i - 1][j].second, next.second)};
		}
	}

	int x, y, a, b, c, d;
	cin >> x >> y >> a >> b >> c >> d;

	++m;
	vector < int > ans;
	for (int i = 1; i <= m; ++i) {
		int z = lca(x, y);
		if (i >= m - p + 1) ans.emplace_back(z);

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

	reverse(ans.begin(), ans.end());
	for (int i = 0; i < p; ++i) {
		cout << ans[i] << "\n";
	}
	return 0;
}