Cod sursa(job #2973227)

Utilizator rares89_Dumitriu Rares rares89_ Data 31 ianuarie 2023 15:22:55
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("atac.in");
ofstream fout("atac.out");

int n, m, p, T[20][32005], cost[20][32005], niv[32005], ind, start[32005], sf[32005];
int nod1, nod2, a, b, c, d;
vector<int> G[32005];

void dfs(int nod, int nivel = 1) {
    niv[nod] = nivel;
    start[nod] = ++ind;
    for(auto i : G[nod]) {
        dfs(i, nivel + 1);
    }
    sf[nod] = ++ind;
}

void precalc() {
    for(int i = 1; (1 << i) <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cost[i][j] = min(cost[i - 1][j], cost[i - 1][T[i - 1][j]]);
            T[i][j] = T[i - 1][T[i - 1][j]];
        }
    }
}

bool valid(int x, int y) { // verific daca x este stramos al lui y
    return start[x] <= start[y] && sf[y] <= sf[x];
}

int detLca(int x, int y) {
    if(valid(x, y)) {
        return x;
    }
    if(valid(y, x)) {
        return y;
    }
    for(int i = 19; i >= 0; i--) {
        int z = T[i][x];
        if(z != 0 && !valid(z, y)) {
            x = z;
        }
    }
    return T[0][x];
}

int det(int x, int y) {
    if(x == y) {
        return 0;
    }
    int minim = 0x3f3f3f3f, lca = detLca(x, y);
    // determin costul minim de la x la lca sau de la y la lca
    for(int nod : {x, y}) {
        int diff = niv[nod] - niv[lca];
        for(int j = 19; j >= 0; j--) {
            if(diff >= (1 << j)) {
                diff -= (1 << j);
                minim = min(minim, cost[j][nod]);
                nod = T[j][nod];
            }
        }
    }
    return minim;
}

int main() {
    fin >> n >> m >> p;
    for(int i = 2; i <= n; i++) {
        fin >> T[0][i] >> cost[0][i];
        G[T[0][i]].push_back(i);
    }
    dfs(1);
    precalc();
    fin >> nod1 >> nod2 >> a >> b >> c >> d;
    for(int i = 1; i <= m; i++) {
        int ans = det(nod1, nod2);
        if(m - i + 1 <= p) {
            fout << ans << "\n";
        }
        nod1 = (nod1 * a + nod2 * b) % n + 1;
        nod2 = (nod2 * c + ans * d) % n + 1;
    }
    return 0;
}