Pagini recente » Cod sursa (job #592245) | Cod sursa (job #914761) | Cod sursa (job #2649434) | Cod sursa (job #665761) | Cod sursa (job #2477176)
// Cotor trebuie sa imi pupe picioarele ca i-am zis ca nu trebe sa bage HPD
#include <bits/stdc++.h>
using namespace std;
void DFS(int node, const vector<vector<pair<int, int>>> &adj,
vector<vector<int>> &rmq, vector<vector<int>> &anc, vector<int> &lvl) {
for (int bit = 1; bit < (int)rmq[node].size(); ++bit) {
int aux = anc[node][bit - 1];
if (aux == -1 || anc[aux][bit - 1] == -1) break;
anc[node][bit] = anc[aux][bit - 1];
rmq[node][bit] = min(rmq[node][bit - 1], rmq[aux][bit - 1]);
}
for (auto &e : adj[node]) {
int x, cost; tie(x, cost) = e;
anc[x][0] = node;
rmq[x][0] = cost;
lvl[x] = lvl[node] + 1;
DFS(x, adj, rmq, anc, lvl);
}
}
int main() {
ifstream cin("atac.in");
ofstream cout("atac.out");
int n, m, p; cin >> n >> m >> p;
vector<vector<pair<int, int>>> adj(n);
for (int i = 0; i < n - 1; ++i) {
int dad, val; cin >> dad >> val; --dad;
adj[dad].emplace_back(i + 1, val);
}
int logn = 32 - __builtin_clz(n);
vector<vector<int>> rmq(n, vector<int>(logn)), anc(n, vector<int>(logn, -1));
vector<int> lvl(n);
DFS(0, adj, rmq, anc, lvl);
auto Query = [&](int x, int y) {
if (x == y) return 0;
int ans = (int)1e9 + 6;
if (lvl[x] > lvl[y]) swap(x, y);
int dist = lvl[y] - lvl[x];
for (int bit = 0; dist != 0; ++bit) {
if (dist & (1 << bit)) {
ans = min(ans, rmq[y][bit]);
y = anc[y][bit];
dist ^= 1 << bit;
}
}
if (x == y) return ans;
for (int bit = logn - 1; bit >= 0; --bit) {
if (anc[x][bit] == anc[y][bit]) continue;
ans = min({ans, rmq[x][bit], rmq[y][bit]});
x = anc[x][bit];
y = anc[y][bit];
}
assert(anc[x][0] == anc[y][0]);
ans = min({ans, rmq[x][0], rmq[y][0]});
return ans;
};
int x, y, a, b, c, d; cin >> x >> y >> a >> b >> c >> d;
for (int i = 0; i < m; ++i) {
int ans = Query(x - 1, y - 1);
if (i >= m - p) cout << ans << '\n';
x = (x * a + y * b) % n + 1;
y = (y * c + ans * d) % n + 1;
}
}