Cod sursa(job #3165080)

Utilizator Mihai_PopescuMihai Popescu Mihai_Popescu Data 5 noiembrie 2023 13:22:49
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.07 kb
#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;
}