Pagini recente » Cod sursa (job #685272) | Cod sursa (job #685357) | Cod sursa (job #763810) | Cod sursa (job #2431693) | Cod sursa (job #1702965)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const int N_MAX = 32001;
const int LOG_MAX = 16;
const int INF = 0x7fffffff;
vector<pair<int, int>> graph[N_MAX];
int f[LOG_MAX][N_MAX], c[LOG_MAX][N_MAX], depth[N_MAX];
void Dfs(int crt, int p) {
depth[crt] = depth[p] + 1;
for(auto nxt : graph[crt]) {
if(nxt.first != p) {
f[0][nxt.first] = crt;
c[0][nxt.first] = nxt.second;
Dfs(nxt.first, crt);
}
}
}
void Preproc() {
int i, j;
for(i = 1; i < LOG_MAX; i++) {
for(j = 1; j < N_MAX; j++) {
f[i][j] = f[i - 1][f[i - 1][j]];
c[i][j] = min(c[i - 1][j], c[i - 1][f[i - 1][j]]);
}
}
}
int Query(int x, int y) {
int cost = INF, i, depthDif;
if(depth[x] < depth[y])
swap(x, y);
depthDif = depth[x] - depth[y];
for(int i = 0; i < LOG_MAX; i++) {
if(depthDif & (1 << i)) {
cost = min(cost, c[i][x]);
x = f[i][x];
}
}
for(int i = LOG_MAX - 1; i >= 0; i--) {
if(f[i][x] != f[i][y]) {
cost = min(cost, min(c[i][x], c[i][y]));
x = f[i][x];
y = f[i][y];
}
}
cost = min(cost, min(c[0][x], c[0][y]));
if(cost == INF)
return 0;
return cost;
}
int main() {
ifstream f("atac.in");
ofstream g("atac.out");
int N, Q, P, i, j, X, Y, A, B, C, D, Z;
f >> N >> Q >> P;
for(i = 2; i <= N; i++) {
f >> X >> Y;
graph[X].push_back(make_pair(i, Y));
graph[i].push_back(make_pair(X, Y));
}
for(i = 0; i < LOG_MAX; i++)
for(j = 0; j < N_MAX; j++)
c[i][j] = INF;
Dfs(1, 0);
Preproc();
f >> X >> Y >> A >> B >> C >> D;
for(i = 1; i <= Q; i++) {
Z = Query(X, Y);
if(Q - P + 1 <= i)
g << Z << '\n';
X = (int64_t(X) * A + int64_t(Y) * B) % N + 1;
Y = (int64_t(Y) * C + int64_t(Z) * D) % N + 1;
}
return 0;
}