Pagini recente » Cod sursa (job #3128413) | Cod sursa (job #928330) | Cod sursa (job #1790126) | Cod sursa (job #1098473) | Cod sursa (job #1536103)
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 32000;
const int kMaxLog = 15;
vector <pair<int, int>> adj[kMaxN];
int d[kMaxLog][kMaxN];
int c[kMaxLog][kMaxN];
int depth[kMaxN];
void DFS(int u) {
for (auto son : adj[u]) {
if (!depth[son.first]) {
depth[son.first] = depth[u] + 1;
d[0][son.first] = u;
c[0][son.first] = son.second;
DFS(son.first);
}
}
}
int main(void) {
ifstream in("atac.in");
ofstream out("atac.out");
in.tie(0);
ios_base::sync_with_stdio(0);
int N, Q, P;
int U, V, A, B, C, D;
in >> N >> Q >> P;
for (int i = 1; i < N; i++) {
in >> U >> V;
adj[U - 1].emplace_back(make_pair(i, V));
adj[i].emplace_back(make_pair(U - 1, V));
}
in >> U >> V >> A >> B >> C >> D;
in.close();
depth[0] = 1;
DFS(0);
for (int i = 1; (1 << i) <= N; i++) {
for (int j = 0; j < N; j++) {
int ancestor = d[i - 1][j];
d[i][j] = d[i - 1][ancestor];
c[i][j] = min(c[i - 1][j], c[i - 1][ancestor]);
}
}
auto solveQuery = [] (int u, int v) -> int {
auto fastLg = [] (const int &X) -> int {
return 31 - __builtin_clz(X);
};
if (u == v) {
return 0;
}
if (depth[u] > depth[v]) {
swap(u, v);
}
int q = numeric_limits <int> :: max();
for (int k = fastLg(depth[v]); k >= 0; k--) {
if (depth[u] + (1 << k) <= depth[v]) {
q = min(q, c[k][v]);
v = d[k][v];
}
}
if (u != v) {
for (int k = fastLg(depth[u]); k >= 0; k--) {
if (d[k][u] && d[k][u] != d[k][v]) {
q = min(q, min(c[k][u], c[k][v]));
u = d[k][u]; v = d[k][v];
}
}
q = min(q, min(c[0][u], c[0][v]));
}
return q;
};
while (Q--) {
int ans = solveQuery(U - 1, V - 1);
if (Q < P) {
out << ans << '\n';
}
U = (U * A + V * B) % N + 1;
V = (V * C + ans * D) % N + 1;
}
out.close();
return 0;
}