Pagini recente » Cod sursa (job #3361088) | Cod sursa (job #3361070) | Borderou de evaluare (job #3027302) | Cod sursa (job #3361136)
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
ifstream fin ("atac.in");
ofstream fout ("atac.out");
const int NMAX = 32e3, LOG = 16;
int n, m, p, up[NMAX + 5][LOG + 5], dt[NMAX + 5], cost_min[NMAX + 5][LOG + 5], x, y, a, b, c, d;
bool has_parent[NMAX + 5];
vector <int> g[NMAX + 5];
void dfs (int node) {
for (auto nx : g[node]) {
dt[nx] = dt[node] + 1;
dfs (nx);
}
}
int lca (int u, int v) {
if (u == v)
return 0;
int ans = 1e9;
if (dt[u] < dt[v])
swap(u, v);
int diff = dt[u] - dt[v];
for (int i = LOG; i >= 0; i--) {
if (diff & (1 << i)) {
ans = min (ans, cost_min[u][i]);
u = up[u][i];
}
}
if (u == v)
return ans;
for (int i = LOG; i >= 0; i--) {
if (up[u][i] != up[v][i]) {
ans = min(ans, cost_min[u][i]);
ans = min(ans, cost_min[v][i]);
u = up[u][i];
v = up[v][i];
}
}
return min ({ans, cost_min[u][0], cost_min[v][0]});
}
int main() {
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
fin >> n >> m >> p;
for (int i = 2; i <= n; i++) {
int u, v;
fin >> u >> v;
has_parent[i] = true;
up[i][0] = u;
cost_min[i][0] = v;
g[u].push_back(i); // parinte -> copil
}
for (int j = 1; j <= LOG; j++) {
for (int i = 1; i <= n; i++)
cost_min[i][j] = 1e9;
}
for (int j = 1; j <= LOG; j++) {
for (int i = 1; i <= n; i++) {
up[i][j] = up[up[i][j - 1]][j - 1];
cost_min[i][j] = min (cost_min[i][j - 1], cost_min[up[i][j - 1]][j - 1]);
}
}
dt[1] = 0;
int root = 1; // radacina n are parinte!!
while (has_parent[root])
root++;
dfs (root);
fin >> x >> y >> a >> b >> c >> d;
for (int i = 1; i <= m; i++) {
int z = lca (x, y);
if (m - i + 1 <= p)
fout << z << "\n";
x = (1LL * x * a + 1LL * y * b) % n + 1;
y = (1LL * y * c + 1LL * z * d) % n + 1;
}
return 0;
}