Cod sursa(job #1958661)

Utilizator preda.andreiPreda Andrei preda.andrei Data 8 aprilie 2017 16:09:43
Problema Atac Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.72 kb
#include <fstream>
#include <vector>

using namespace std;

const int kLog = 30;

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

    int costs[kLog];
    int costs_len = 0;

    int enter_time = 0, exit_time = 0;
    vector<pair<int, int>> edges;
};

using Tree = vector<Node>;

int dfs_time = 0;

void Dfs(Tree &t, int node, vector<int> &st, int &nst)
{
    t[node].enter_time = ++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; fa > 0 && i < t[fa].anc_len; ++i) {
            t[node].ancestors[i] = t[fa].ancestors[i - 1];
            t[node].costs[i] = min(t[node].costs[i - 1], t[fa].costs[i - 1]);

            fa = t[fa].ancestors[i - 1];
            t[node].anc_len = t[node].costs_len = i + 1;
        }
    }

    for (const auto &e : t[node].edges) {
        int son = e.first;
        if (t[son].enter_time == 0) {
            t[son].costs[0] = e.second;
            t[son].costs_len = 1;
            Dfs(t, son, st, nst);
        }
    }
    t[node].exit_time = ++dfs_time;
    --nst;
}

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

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

    int min_cost = (1 << 29);
    while (x != y) {
        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;
                    min_cost = min(min_cost, t[x].costs[pos]);
                }
            }
            pow >>= 1;
        }
        x = t[x].ancestors[pos];
    }
    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].edges.push_back({fa - 1, cost});
        tree[fa - 1].edges.push_back({i, cost});
    }

    FindAncestors(tree);

    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));
        if (q - i + 1 <= 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;
}