Cod sursa(job #2959495)

Utilizator domistnSatnoianu Dominic Ioan domistn Data 31 decembrie 2022 15:11:27
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 32000, LGMAX = 16;

int n, m, p, x, y, a, b, c, d,
    niv[NMAX + 1], lgAbove[NMAX + 1][LGMAX + 1],
    sparseStrazi[NMAX + 1][LGMAX + 1];
vector<int> adj[NMAX + 1];

void calculateNiv(int nod = 1, int nivCrt = 0) {
    niv[nod] = nivCrt;
    for(const auto &el : adj[nod])
        calculateNiv(el, nivCrt + 1);
}

void calculateSparse() {
    for(int sz = 1; (1 << sz) <= n; ++sz)
        for(int i = 1; i <= n; ++i)
            lgAbove[i][sz] = lgAbove[lgAbove[i][sz - 1]][sz - 1],
            sparseStrazi[i][sz] = min(sparseStrazi[i][sz - 1],
                                      sparseStrazi[lgAbove[i][sz - 1]][sz - 1]);
}

int main()
{
    freopen("atac.in", "r", stdin);
    freopen("atac.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &p);
    for(int i = 2, x, y; i <= n; ++i) {
        scanf("%d%d", &x, &y); //x este tatal lui i, lungime y
        adj[x].push_back(i);
        lgAbove[i][0] = x;
        sparseStrazi[i][0] = y;
    }

    calculateNiv();
    calculateSparse();

    scanf("%d%d%d%d%d%d", &x, &y, &a, &b, &c, &d);
    int ans = 0;
    for(int i = 1; i <= m; ++i) {
        if(x == y) ans = 0;
        else {
            ans = 2e9;
            int cx = x, cy = y;
            if(niv[cx] < niv[cy]) swap(cx, cy);
            int nivDif = niv[cx] - niv[cy];
            for(int i = 0; i <= LGMAX; ++i)
                if((1 << i) & nivDif) {
                    ans = min(ans, sparseStrazi[cx][i]);
                    cx = lgAbove[cx][i];
                }
            //acum sunt la acelasi nivel
            for(int i = 0; i <= LGMAX; ++i)
                if(lgAbove[cx][i] != lgAbove[cy][i]) { //le aducem la cel mai mare nivel (cel mai jos punct) in care au un ancestor comun adica la lca
                    ans = min(ans, sparseStrazi[cx][i]);
                    ans = min(ans, sparseStrazi[cy][i]);
                    cx = lgAbove[cx][i];
                    cy = lgAbove[cy][i];
                }
            if(cx != cy)
                ans = min(ans, sparseStrazi[cx][0]),
                ans = min(ans, sparseStrazi[cy][0]);
        }
        if(i >= m - p + 1) printf("%d\n", ans);

        x = (1ll * x * a + y * b) % n + 1;
        y = (1ll * y * c + ans * d) % n + 1;
    }
    return 0;
}