Pagini recente » Cod sursa (job #1620418) | Cod sursa (job #937804) | Cod sursa (job #1149547) | Cod sursa (job #545890) | Cod sursa (job #1535968)
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 32000;
const int kMaxLog = 15;
const int NIL = -1;
struct Edge {
int v;
int next;
};
Edge l[kMaxN - 1];
int adj[kMaxN];
int d[kMaxLog][kMaxN];
int c[kMaxLog][kMaxN];
int depth[kMaxN];
void DFS(int u) {
for (int i = adj[u]; i != NIL; i = l[i].next) {
if (l[i].v != d[0][u]) {
depth[l[i].v] = depth[u] + 1;
DFS(l[i].v);
}
}
}
int main(void) {
ifstream in("atac.in");
ofstream out("atac.out");
in.tie(0);
ios_base::sync_with_stdio(0);
int N, Q, printQuery;
int u, v, A, B, C, D;
int oldU, oldV;
in >> N >> Q >> printQuery;
memset(adj, NIL, sizeof(adj));
for (int i = 1; i < N; i++) {
auto addEdge = [] (const int &U, const int &V, const int &ptr) -> void {
l[ptr].v = V;
l[ptr].next = adj[U];
adj[U] = ptr;
};
in >> d[0][i] >> c[0][i];
d[0][i]--;
addEdge(d[0][i], i, i - 1);
}
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];
c[i][j] = min(c[i - 1][ancestor], c[i - 1][j]);
d[i][j] = d[ancestor][j];
}
}
in >> u >> v >> A >> B >> C >> D;
while (Q--) {
auto fastLg = [] (const int &X) {
return 31 - __builtin_clz(X);
};
oldU = u; oldV = v;
u--; v--;
if (depth[u] > depth[v]) {
swap(u, v);
}
int minCost = 0;
if (u != v) {
minCost = numeric_limits <int> :: max();
for (int k = fastLg(depth[v]); k >= 0; k--) {
if (depth[v] - (1 << k) >= depth[u]) {
minCost = min(c[k][v], minCost);
v = d[k][v];
}
}
for (int k = fastLg(depth[u]); k >= 0; k--) {
if (d[k][u] && d[k][u] != d[k][v]) {
minCost = min(min(c[k][u], c[k][v]), u);
u = d[k][u];
v = d[k][v];
}
}
minCost = min(min(c[0][u], c[0][v]), minCost);
u = d[0][u];
}
if (Q < printQuery) {
out << minCost << '\n';
}
u = (oldU * A + oldV * B) % N + 1;
v = (oldV * C + minCost * D) % N + 1;
}
out.close();
return 0;
}