Cod sursa(job #3269672)

Utilizator MihaiZ777MihaiZ MihaiZ777 Data 20 ianuarie 2025 13:35:17
Problema Atac Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

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

#define MAXN 32005

struct Edge {
	int node;
	int c;
};

int n, m, p;
int X, Y, A, B, C, D, Z;

vector<Edge> graph[MAXN];
int ancestors[16][MAXN];
int rmq[16][MAXN];
int depth[MAXN];

void ReadData() {
	memset(rmq, 0x3f3f3f3f, sizeof rmq);
	fin >> n >> m >> p;
	for (int i = 2; i <= n; i++) {
		int u, cost;
		fin >> u >> cost;
		ancestors[0][i] = u;
		rmq[0][i] = cost;
		graph[u].push_back({i, cost});
	}
	fin >> X >> Y >> A >> B >> C >> D;
}

void BuildAncestors(Edge node, int h) {
	depth[node.node] = h;
	for (int e = 1; e < 16; e++) {
		ancestors[e][node.node] = ancestors[e - 1][ancestors[e - 1][node.node]];
		rmq[e][node.node] = min(rmq[e - 1][node.node],
				rmq[e - 1][ancestors[e - 1][node.node]]);
	}
	for (Edge newNode : graph[node.node]) {
		BuildAncestors(newNode, h + 1);
	}
}

int ComputeLCA(int a, int b) {
	if (depth[a] < depth[b]) {
		swap(a, b);
	}
	int ans = 0x3f3f3f3f;
	int dif = depth[a] - depth[b];
	for (int e = 0; e < 16; e++) {
		if ((1 << e) & dif) {
			ans = min(ans, rmq[e][a]);
			a = ancestors[e][a];
		}
	}
	if (a == b) {
		return ans;
	}
	int savedA = a;
	int savedB = b;

	for (int e = 15; e >= 0; e--) {
		if (ancestors[e][a] == ancestors[e][b]) {
			continue;
		}
		a = ancestors[e][a];
		b = ancestors[e][b];
	}

	int lca = ancestors[0][a];
	a = savedA;
	b = savedB;
	dif = depth[a] - depth[lca];
	for (int e = 0; e < 16; e++) {
		if ((1 << e) & dif) {
			ans = min(ans, rmq[e][a]);
			a = ancestors[e][a];
		}
	}
	dif = depth[b] - depth[lca];
	for (int e = 0; e < 16; e++) {
		if ((1 << e) & dif) {
			ans = min(ans, rmq[e][b]);
			b = ancestors[e][b];
		}
	}
	return ans;
}

void Solve() {
	for (int i = 0; i < m; i++) {
		Z = ComputeLCA(X, Y);
		X = (X * A + Y * B) % n + 1;
		Y = (Y * C + Z * D) % n + 1;
		if (m - i <= p) {
			fout << Z << '\n';
		}
	}
}

int main() {
	ReadData();
	BuildAncestors({1, 0}, 1);
	Solve();
	return 0;
}