Cod sursa(job #2400551)

Utilizator lupulescu2001Lupulescu Vlad lupulescu2001 Data 8 aprilie 2019 20:44:57
Problema Atac Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.86 kb
#include <fstream>
#include <cmath>
#include <vector>

using namespace std;

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

const int oo = 2000000000;
const int nMax = 32000;
int n, m, p, a, b, c, d, x, y;
vector<pair<int, int>> g[nMax + 5];
int sol[500005];
int use[nMax + 5], eulvl[2 * nMax + 5], eul[2 * nMax + 5], first[nMax + 5];
int lvl[nMax + 5], dim, cost[20][nMax + 5], st[20][nMax + 5];
int rmq[20][2 * nMax + 5];

void DFS(int nod, int lev) {
    use[nod] = 1;
    lvl[nod] = lev;
    eul[++dim] = nod;
    eulvl[dim] = lev;
    first[nod] = dim;
    for (auto i : g[nod])
        if (!use[i.first]) {
            st[0][i.first] = nod;
            cost[0][i.first] = i.second;
            DFS(i.first, lev + 1);
            eul[++dim] = nod;
            eulvl[dim] = lev;
        }
}

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

void RMQ() {
    for (int i = 1; i <= dim; i++)
        rmq[0][i] = i;
    for (int i = 1; (1 << i) < dim; i++)
        for (int j = 1; j <= dim - (1 << i); j++) {
            rmq[i][j] = rmq[i - 1][j];
            int salt = 1 << (i - 1);
            if (eulvl[rmq[i][j]] > eulvl[rmq[i - 1][j + salt]])
                rmq[i][j] = rmq[i - 1][j + salt];
        }
}

int LCA(int s, int k) {
    s = first[s];
    k = first[k];
    if (s > k)
        swap(s, k);
    int dif = k - s + 1;
    int lg = log2(dif);
    int sol = rmq[lg][s];
    if (eulvl[sol] > eulvl[rmq[lg][k - (1 << lg) + 1]])
        sol = rmq[lg][k -(1 << lg) + 1];
    return eulvl[sol];
}

int main() {
    fin >> n >> m >> p;
    for (int i = 2; i <= n; i++) {
        int u, v;
        fin >> u >> v;
        g[u].push_back({i, v});
        g[i].push_back({u, v});
    }
    fin >> x >> y >> a >> b >> c >> d;
    DFS(1, 0);
    RMQ();
    Build();
    for (int i = 1; i <= m; i++) {
        int stlvl = LCA(x, y);
        int keepx = x, keepy = y;
        int xl = - (stlvl - lvl[x]);
        int yl = - (stlvl - lvl[y]);
        int urc = 0;
        sol[i] = oo;
        while (xl > 0 && x > 0) {
            if (xl & 1) {
                sol[i] = min(sol[i], cost[urc][x]);
                x = st[urc][x];
            }
            urc++;
            xl /= 2;
        }
        urc = 0;
        while (yl > 0 && y > 0) {
            if (yl & 1) {
                sol[i] = min(sol[i], cost[urc][y]);
                y = st[urc][y];
            }
            urc++;
            yl /= 2;
        }
        if (sol[i] == oo)
        sol[i] = 0;
        x = (keepx * a + keepy * b) % n + 1;
        y = (keepy * c + sol[i] * d) % n + 1;
    }
    for (int i = m - p + 1; i <= m; i++)
        fout << sol[i] << '\n';
}