Pagini recente » Cod sursa (job #10421) | Cod sursa (job #20800) | Cod sursa (job #61709) | Cod sursa (job #37658) | Cod sursa (job #3207213)
#include <bits/stdc++.h>
using namespace std;
const char nl = '\n';
const char sp = ' ';
const int inf = 0x3f3f3f3f;
const int mod = 30011;
const char out[2][4]{ "NO", "YES" };
#define all(a) a.begin(), a.end()
using ll = long long;
ifstream fin("atac.in");
ofstream fout("atac.out");
const int nmax = 32000;
const int lgmax = 15;
int n, m, p;
vector<pair<int, int>> g[nmax + 5];
int depth[nmax + 5]{ 0 };
int t[lgmax][nmax + 5]{ 0 };
int rmq[lgmax][nmax + 5]{ 0 };
void compute(int u, int p = -1) {
for (auto& e : g[u]) {
int v = e.first, w = e.second;
if (v == p) {
continue;
}
depth[v] = depth[u] + 1;
t[0][v] = u;
rmq[0][v] = w;
for (int p = 1; p < lgmax; ++p) {
if (t[p - 1][v] == 0 || t[p - 1][t[p - 1][v]] == 0) {
break;
}
t[p][v] = t[p - 1][t[p - 1][v]];
rmq[p][v] = min(rmq[p - 1][v], rmq[p - 1][t[p - 1][v]]);
}
compute(v, u);
}
}
pair<int, int> kth(int x, int k) {
// returns the k-th ancestor of x and the minimum edge of the path between x and it's ancestor
if (k == 0) {
return { x, inf };
}
pair<int, int> res{ x, inf };
for (int bit = 0; (1 << bit) <= k; ++bit) {
if ((k >> bit) & 1) {
res.second = min(res.second, rmq[bit][res.first]);
res.first = t[bit][res.first];
}
}
return res;
}
int query(int x, int y) {
if (x == y) {
return 0;
}
if (depth[x] > depth[y]) { // x sa fie mai sus decat y
swap(x, y);
}
int ans = inf;
if (depth[x] != depth[y]) { // x si y sa fie la acelasi nivel
tie(y, ans) = kth(y, depth[y] - depth[x]);
}
if (x == y) {
return ans;
}
for (int p = lgmax - 1; p >= 0; --p) {
if (t[p][x] != t[p][y]) { // urc nodurile simultan
ans = min(ans, min(rmq[p][x], rmq[p][y]));
x = t[p][x];
y = t[p][y];
}
}
return min(ans, min(rmq[0][x], rmq[0][y]));
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
fin >> n >> m >> p;
for (int i = 2; i <= n; ++i) {
int j, w;
fin >> j >> w;
g[i].push_back({ j, w });
g[j].push_back({ i, w });
}
compute(1);
ll x, y, a, b, c, d;
fin >> x >> y >> a >> b >> c >> d;
for (int q = 1; q <= m; ++q) {
ll z = query(x, y);
if (m - q + 1 <= p) {
fout << z << nl;
}
x = (a * x + b * y) % n + 1;
y = (c * y + d * z) % n + 1;
}
}