Pagini recente » Cod sursa (job #508410) | Cod sursa (job #1890859) | Cod sursa (job #2770697) | Cod sursa (job #2763500) | Cod sursa (job #3165080)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("atac.in");
ofstream fout("atac.out");
#define NMAX 32005
vector<int> G[NMAX];
int stramos[20][NMAX], dp[20][NMAX];
int nivel[NMAX];
void dfs(int nod) {
for (auto it : G[nod]) {
nivel[it] = nivel[nod] + 1;
dfs(it);
}
}
int lca(int x, int y) {
int minim = 1e9;
if (nivel[x] < nivel[y]) {
int aux = x;
x = y;
y = aux;
}
int dif = nivel[x] - nivel[y];
for (int i = 0; (1 << i) <= dif; ++i) {
if (dif & (1 << i)) {
minim = min(minim, dp[i][x]);
x = stramos[i][x];
}
}
for (int log = 19; log >= 0; --log) {
if (stramos[log][x] != stramos[log][y]) {
if (dp[log][x] < minim) {
minim = dp[log][x];
}
if (dp[log][y] < minim) {
minim = dp[log][y];
}
x = stramos[log][x];
y = stramos[log][y];
}
}
if (x != y) {
minim = min(minim, min(dp[0][x], dp[0][y]));
}
if (minim == 1e9) {
minim = 0;
}
return minim;
}
int main() {
int n, m, p;
fin >> n >> m >> p;
for (int i = 2; i <= n; ++i) {
int u, v;
fin >> u >> v;
stramos[0][i] = u;
dp[0][i] = v;
G[u].push_back(i);
}
int x, y, a, b, c, d;
fin >> x >> y >> a >> b >> c >> d;
for (int i = 1; (1 << i) <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (stramos[i - 1][j]) {
stramos[i][j] = stramos[i - 1][stramos[i - 1][j]];
}
if (dp[i - 1][j]) {
dp[i][j] = min(dp[i - 1][stramos[i - 1][j]], dp[i - 1][j]);
}
}
}
nivel[1] = 1;
dfs(1);
for (int i = 1; i <= m; ++i) {
int nr = lca(x, y);
x = (x * a + y * b) % n + 1;
y = (y * c + nr * d) % n + 1;
if (i >= m - p + 1) {
fout << nr << '\n';
}
}
return 0;
}