Cod sursa(job #1958625)

Utilizator preda.andreiPreda Andrei preda.andrei Data 8 aprilie 2017 15:39:58
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <fstream>
#include <vector>

using namespace std;

const int kLog = 20;

struct Node
{
    int ancestors[kLog];
    int anc_len = 0;

    int exit_time;
    int father_cost;
    vector<int> edges;
};

using Tree = vector<Node>;

int dfs_time = 0;

void Dfs(Tree &t, int node, vector<int> &st, int &nst)
{
    ++dfs_time;
    st[nst++] = node;

    if (nst != 1) {
        int fa = st[nst - 2];
        t[node].ancestors[0] = fa;
        t[node].anc_len = 1;

        for (int i = 1; (1 << i) < nst; ++i) {
            t[node].ancestors[i] = t[fa].ancestors[i - 1];
            fa = t[fa].ancestors[i - 1];
            t[node].anc_len = i + 1;
        }
    }

    for (const auto &son : t[node].edges) {
        Dfs(t, son, st, nst);
    }
    t[node].exit_time = ++dfs_time;
    --nst;
}

void FindAncestors(Tree &t, int root)
{
    vector<int> st(t.size());
    int nst = 0;
    Dfs(t, root, st, nst);
}

int FindLca(const Tree &t, int x, int y)
{
    if (x == y) {
        return x;
    }

    if (t[x].exit_time > t[y].exit_time) {
        swap(x, y);
    }

    int pos = 0;
    int pow = (1 << 20);

    while (pow > 0) {
        if (pow + pos < t[x].anc_len) {
            int fa = t[x].ancestors[pos + pow];
            if (t[fa].exit_time < t[y].exit_time) {
                pos += pow;
            }
        }
        pow >>= 1;
    }
    return FindLca(t, y, t[x].ancestors[pos]);
}

int FindMin(const Tree &t, int x, int y)
{
    int lca = FindLca(t, x, y);
    int min_cost = (1 << 25);

    while (x != lca) {
        min_cost = min(min_cost, t[x].father_cost);
        x = t[x].ancestors[0];
    }

    while (y != lca) {
        min_cost = min(min_cost, t[y].father_cost);
        y = t[y].ancestors[0];
    }
    return min_cost;
}

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

    int n, q, p;
    fin >> n >> q >> p;

    Tree tree(n);
    for (int i = 1; i < n; ++i) {
        int fa, cost;
        fin >> fa >> cost;
        tree[i].father_cost = cost;
        tree[fa - 1].edges.push_back(i);
    }

    FindAncestors(tree, 0);

    int x, y, a, b, c, d;
    fin >> x >> y >> a >> b >> c >> d;

    for (int i = 1; i <= q; ++i) {
        int res = ((x == y) ? 0 : FindMin(tree, x - 1, y - 1));
//        fout << x << " " << y << "\n";
//        fout << "lca = " << FindLca(tree, x - 1, y - 1) + 1 << "\n";
        if (q - i <= p) {
            fout << res << "\n";
        }

        int new_x = (x * a + y * b) % (n + 1);
        int new_y = (y * c + res * d) % (n + 1);
        x = new_x;
        y = new_y;
    }

    return 0;
}