Cod sursa(job #3359341)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 27 iunie 2026 12:09:42
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.92 kb
#include <bits/stdc++.h>

using namespace std;

int stramos[32001][15];
int cost_min[32001][15];
vector<int> adj[32001];
int d[32001];

void dfs(int node) {
    for(auto it : adj[node]) {
        d[it] = d[node] + 1;
        dfs(it);
    }
}

int lca(int x, int y) {
    if(x == y) {
        return 0;
    }
    if(d[x] < d[y]) {
        swap(x, y);
    }
    int minim = 1e9;
    int dif = d[x] - d[y];
    for(int b = 0; b <= 14; b++) {
        if((1 << b) & dif) {
            minim = min(minim, cost_min[x][b]);
            x = stramos[x][b];
        }
    }
    if(x == y) {
        return minim;
    }
    for(int b = 14; b >= 0; b--) {
        if(stramos[x][b] != stramos[y][b]) {
            minim = min(minim, min(cost_min[x][b], cost_min[y][b]));
            x = cost_min[x][b];
            y = cost_min[y][b];
        }
    }
    minim = min(minim, min(cost_min[x][0], cost_min[y][0]));
    return minim;
}

int main() {
    ifstream cin("atac.in");
    ofstream cout("atac.out");
    int n, m, p;
    cin >> n >> m >> p;
    for(int j = 0; j <= 14; j++) {
        for(int i = 1; i <= n; i++) {
            cost_min[i][j] = 1e9;
        }
    }
    for(int i = 2; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        cost_min[i][0] = y;
        stramos[i][0] = x;
        adj[x].push_back(i);
    }
    dfs(1);
    for(int j = 1; j <= 14; j++) {
        for(int i = 1; i <= n; i++) {
            stramos[i][j] = stramos[stramos[i][j - 1]][j - 1];
            if((1 << j) <= d[i]) {
                cost_min[i][j] = min(cost_min[i][j - 1], cost_min[stramos[i][j - 1]][j - 1]);
            }
        }
    }

    int x, y, a, b, c, d;
    cin >> x >> y >> a >> b >> c >> d;
    for(int i = 1; i <= m; i++) {
        int z = lca(x, y);
        if(m - i + 1 <= p) {
            cout << z << '\n';
        }
        x = (1LL * x * a + 1LL * y * b) % n + 1;
        y = (1LL * y * c + 1LL * z * d) % n + 1;
        //break;
    }
    return 0;
}