Cod sursa(job #2285992)

Utilizator ContDeRacistAliniateEBlat ContDeRacist Data 19 noiembrie 2018 17:51:36
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream cin("atac.in");
ofstream cout("atac.out");

const int N = 33007;

vector < pair < int, int > > v[N];
vector < int > euler;

int pl[N], h[N], l[2 * N], cst[N], t[N], rl[2 * N][15], str[N][15], rf[N][15];
int in, n;

void pe_dfs(int nod = 1) {
    euler.push_back(nod);
    if (pl[nod] == 0)
        pl[nod] = euler.size() - 1;
    for (auto i : v[nod])
        h[i.first] = h[nod] + 1, pe_dfs(i.first), euler.push_back(nod);
}

void precalc() {
    pe_dfs();
    for (int i = 0; i < 15; ++i)
        for (int j = (1<<i); j < (1<<(i + 1)) && j < N; ++j)
            l[j] = i;
    for (int i = 0; i < euler.size(); ++i)
        rl[i][0] = euler[i];
    for (int i = 1; i <= n; ++i)
        str[i][0] = t[i];
    for (int i = 2; i <= n; ++i)
        rf[i][0] = cst[i];
    for (int p = 1; p < 15; ++p) {
        for (int i = 0; i + (1<<p) <= euler.size(); ++i) {
            if (h[rl[i][p - 1]] < h[rl[i + (1<<(p - 1))][p - 1]])
                rl[i][p] = rl[i][p - 1];
            else
                rl[i][p] = rl[i + (1<<(p - 1))][p - 1];
        }
        for (int i = 1; i <= n; ++i)
            str[i][p] = str[str[i][p - 1]][p - 1],
            rf[i][p] = min(rf[i][p - 1], rf[str[i][p - 1]][p - 1]);
    }
}

int lca(int x, int y) {
    if (pl[x] > pl[y])
        swap(x, y);
    if (h[rl[pl[x]][l[pl[y] - pl[x] + 1]]] > h[rl[pl[y] - (1<<l[pl[y] - pl[x] + 1]) + 1][l[pl[y] - pl[x] + 1]]])
        return rl[pl[y] - (1<<l[pl[y] - pl[x] + 1]) + 1][l[pl[y] - pl[x] + 1]];
    return rl[pl[x]][l[pl[y] - pl[x] + 1]];
}

int f(int x, int y) {
    if (y == 0)
        return 0;
    if (h[x] < y)
        return 0;
    int r(0), pas = 14, ans(1e9 + 7);
    while (pas >= 0) {
        if (r + (1<<pas) <= y)
            ans = min(ans, rf[x][pas]),
            r += (1<<pas),
            x = str[x][pas];
        --pas;
    }
    return ans;
}

int main()
{
    int q, p, x, y, a, b, c, d;
    cin >> n >> q >> p;
    for (int i = 2; i <= n; ++i)
        cin >> t[i] >> cst[i],
        v[t[i]].push_back({i, cst[i]});
    precalc();

    cin >> x >> y >> a >> b >> c >> d;
    while (q--) {
        if (x == y) {
            if (q < p)
                cout << "0\n";
            x = (1LL * x * a + 1LL * y * b) % n + 1;
            y = 1LL * y * c % n + 1;
            continue;
        }

        int piv = lca(x, y);
        int min1 = f(x, h[x] - h[piv]), min2 = f(y, h[y] - h[piv]);
        if (q < p)
            cout << min(min1, min2) << '\n';
        x = (1LL * x * a + 1LL * y * b) % n + 1;
    y = (1LL * y * c + 1LL * min(min1, min2) * d) % n + 1;

    }
    return 0;
}