Cod sursa(job #2286008)

Utilizator ContDeRacistAliniateEBlat ContDeRacist Data 19 noiembrie 2018 18:16:21
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.49 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);
    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 k = 1; k < 15; ++k) {
        for (int i = (1<<k) - 1; i < euler.size(); ++i) {
            rl[i][k] = rl[i][k - 1];
            if (h[rl[i][k]] > h[rl[i - (1<<(k - 1))][k - 1]])
                rl[i][k] = rl[i - (1<<(k - 1))][k - 1];
        }
        for (int i = 1; i <= n; ++i)
            str[i][k] = str[str[i][k - 1]][k - 1],
            rf[i][k] = min(rf[i][k - 1], rf[str[i][k - 1]][k - 1]);
    }
}

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

int f(int x, int y) {
    if (y == 0)
        return 0;
    if (h[x] < y)
        return 0;
    int r(0), pas = 15, 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;
}