Pagini recente » Cod sursa (job #2897013) | Cod sursa (job #2750708) | Cod sursa (job #1378381) | Cod sursa (job #2739732) | Cod sursa (job #2608155)
#include <iostream>
#include <fstream>
#include <vector>
struct node {
struct edge {
int child_id;
int cost;
};
std::vector<edge> children;
int first_euler;
int level;
int cost;
int in, out;
} nodes[32001];
int euler[64002];
int rmq[17][64002];
int log2[64002];
void dfs_euler(int node) {
static int euler_i, time = 1;
euler[++euler_i] = node;
nodes[node].first_euler = euler_i;
nodes[node].in = time++;
for (const auto& edge : nodes[node].children) {
const int child_id = edge.child_id;
auto& child = nodes[child_id];
if (child.first_euler == 0) {
child.level = nodes[node].level + 1;
dfs_euler(child_id);
euler[++euler_i] = node;
}
}
nodes[node].out = time++;
}
inline void compute_log2(int n) {
log2[1] = 0;
for (int i = 2; i <= 2 * n - 1; i++) {
log2[i] = log2[i / 2] + 1;
}
}
int lca(int n, int a, int b) {
int p = nodes[a].first_euler, q = nodes[b].first_euler;
if (p > q) {
std::swap(p, q);
}
int l = log2[q - p + 1];
int st = rmq[l][p + (1 << l) - 1];
int dr = rmq[l][q];
if (nodes[st].level < nodes[dr].level) {
return st;
} else {
return dr;
}
}
int main() {
std::ifstream fin("atac.in");
std::ofstream fout("atac.out");
int n, m, p;
int x, y, a, b, c, d;
fin >> n >> m >> p;
for (int i = 2; i <= n; i++) {
int u, v;
fin >> u >> v;
nodes[u].children.push_back({i, v});
nodes[i].children.push_back({u, v});
}
fin >> x >> y >> a >> b >> c >> d;
compute_log2(n);
dfs_euler(1);
for (int j = 1; j <= 2 * n - 1; j++) {
rmq[0][j] = euler[j];
}
for (int i = 1; (1 << i) <= 2 * n - 1; i++) {
for (int j = 1; j <= 2 * n - 1; j++) {
int st = rmq[i - 1][j - (1 << (i - 1))];
int dr = rmq[i - 1][j];
if (nodes[st].level < nodes[dr].level) {
rmq[i][j] = st;
} else {
rmq[i][j] = dr;
}
}
}
for (int i = m; i > 0; i--) {
int common = lca(n, x, y);
// urca de la x la common
int node = x;
int z = 100001;
while (node != common) {
for (const auto& edge : nodes[node].children) {
const auto& candidate = nodes[edge.child_id];
if (candidate.in < nodes[node].in && candidate.out > nodes[node].out) {
node = edge.child_id;
if (edge.cost < z) {
z = edge.cost;
}
break;
}
}
}
// urca de la y la common
node = y;
while (node != common) {
for (const auto& edge : nodes[node].children) {
const auto& candidate = nodes[edge.child_id];
if (candidate.in < nodes[node].in && candidate.out > nodes[node].out) {
node = edge.child_id;
if (edge.cost < z) {
z = edge.cost;
}
break;
}
}
}
int x_prim = (x * a + y * b) % n + 1;
int y_prim = (y * c + z * d) % n + 1;
x = x_prim;
y = y_prim;
if (i <= p) {
fout << z << '\n';
}
}
return 0;
}