Cod sursa(job #2959457)

Utilizator domistnSatnoianu Dominic Ioan domistn Data 31 decembrie 2022 12:10:50
Problema Atac Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.92 kb
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int NMAX = 32000, PMAX = 10000, LG = 16;

int n, m, p, px, py, a, b, c, d, ans[PMAX + 1], ansl, etl,
    lg2[2 * NMAX + 1], first[NMAX + 1], niv[NMAX + 1], t[NMAX + 1],
    sparseLCA[2 * NMAX + 1][LG + 1], sparseStrazi[NMAX + 1][LG + 1],
    lgAbove[NMAX + 1][LG + 1];
vector<pii> adj[NMAX + 1];
vector<int> eulerTour;

void precalcLg2() {
    lg2[1] = 0;
    for(int i = 2; i <= 2 * NMAX; ++i)
        lg2[i] = lg2[i / 2] + 1;
}

void constructEulerTour(int nod = 1, int par = -1, int nivCrt = 0) {
    niv[nod] = nivCrt;
    first[nod] = eulerTour.size();
    t[nod] = par;
    eulerTour.push_back(nod);
    for(const auto &el : adj[nod]) {
        if(el.first == par) continue;
        constructEulerTour(el.first, nod, nivCrt + 1);
        eulerTour.push_back(nod);
    }
}

void constructLCA() {
    for(int i = 1; i <= etl; ++i)
        sparseLCA[i][0] = eulerTour[i];
    for(int sz = 1; (1 << sz) <= etl; ++sz)
        for(int i = 1; i + (1 << sz) - 1 <= etl; ++i) {
            const int v1 = sparseLCA[i][sz - 1],
                      v2 = sparseLCA[i + (1 << (sz - 1))][sz - 1];
            if(niv[v1] < niv[v2]) sparseLCA[i][sz] = v1;
            else sparseLCA[i][sz] = v2;
        }
}

int lca(int x, int y) {
    x = first[x];
    y = first[y];
    if(x > y) swap(x, y);
    const int lg2dist = lg2[y - x + 1];
    const int v1 = sparseLCA[x][lg2dist],
              v2 = sparseLCA[y - (1 << lg2dist) + 1][lg2dist];
    if(niv[v1] < niv[v2]) return v1;
    return v2;
}

void constructStrazi(int nod = 1) {
    for(int sz = 1; (1 << sz) <= niv[nod]; ++sz) {
        lgAbove[nod][sz] = lgAbove[lgAbove[nod][sz - 1]][sz - 1];
        const int v1 = sparseStrazi[nod][sz - 1],
                  v2 = sparseStrazi[lgAbove[nod][sz - 1]][sz - 1];
        sparseStrazi[nod][sz] = min(v1, v2);
    }
    for(const auto &el : adj[nod]) {
        if(el.first == t[nod]) continue;
        sparseStrazi[el.first][0] = el.second;
        lgAbove[el.first][0] = nod;
        constructStrazi(el.first);
    }
}

int main()
{
    precalcLg2();
    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);
        adj[i].push_back({x, y});
        adj[x].push_back({i, y});
    }

    eulerTour.push_back(0);
    constructEulerTour();
    etl = eulerTour.size() - 1;
    constructLCA();
    sparseStrazi[0][0] = 2e9;
    constructStrazi();

//    for(int i = 1; i <= n; ++i) {
//        cout << i << ": \n";
//        for(int sz = 0; (1 << sz) <= niv[i]; ++sz)
//            cout << sz << " " << lgAbove[i][sz] << " " << sparseStrazi[i][sz] << "\n";
//        cout << "\n";
//    }

    scanf("%d%d%d%d%d%d", &px, &py, &a, &b, &c, &d);
    for(int i = 1; i <= m; ++i) {
        int plca = lca(px, py), lg2dist;
//        cout << px << " " << py << " " << plca << "\n";

        //x - lca
        lg2dist = lg2[niv[px] - niv[plca]];
        int px2 = px;
        for(int i = niv[px] - niv[plca] - (1 << lg2dist); i >= 1; --i)
            px2 = t[px2];
        int min_x_lca = min(sparseStrazi[px][lg2dist],
                            sparseStrazi[px2][lg2dist]);
//        cout << lg2dist << " " << px2 << " " << min_x_lca << "\n";

        //y - lca
        lg2dist = lg2[niv[py] - niv[plca]];
        int py2 = py;
        for(int i = niv[py] - niv[plca] - (1 << lg2dist); i >= 1; --i)
            py2 = t[py2];
        int min_y_lca = min(sparseStrazi[py][lg2dist],
                            sparseStrazi[py2][lg2dist]);
//        cout << lg2dist << " " << py2 << " " << min_y_lca << "\n";
        int ans = min(min_x_lca, min_y_lca);
        if(i >= m - p + 1) cout << ans << "\n";

        px = (px * a + py * b) % n + 1;
        py = (py * c + ans * d) % n + 1;
    }
    return 0;
}