Cod sursa(job #3361136)

Utilizator RuxandraPro12_Metehau Ruxandra Maria RuxandraPro12_ Data 20 iulie 2026 20:55:25
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
#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;
}