Cod sursa(job #2608155)

Utilizator copanelTudor Roman copanel Data 30 aprilie 2020 18:12:16
Problema Atac Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.37 kb
#include <iostream>
#include <fstream>
#include <vector>

struct node {
    struct edge {
        int child_id;
        int cost;
    };
    std::vector<edge> children;
    int first_euler;
    int level;
    int cost;
    int in, out;
} nodes[32001];
int euler[64002];
int rmq[17][64002];
int log2[64002];

void dfs_euler(int node) {
    static int euler_i, time = 1;

    euler[++euler_i] = node;
    nodes[node].first_euler = euler_i;
    nodes[node].in = time++;
    for (const auto& edge : nodes[node].children) {
        const int child_id = edge.child_id;
        auto& child = nodes[child_id];
        if (child.first_euler == 0) {
            child.level = nodes[node].level + 1;
            dfs_euler(child_id);
            euler[++euler_i] = node;
        }
    }
    nodes[node].out = time++;
}

inline void compute_log2(int n) {
    log2[1] = 0;
    for (int i = 2; i <= 2 * n - 1; i++) {
        log2[i] = log2[i / 2] + 1;
    }
}

int lca(int n, int a, int b) {
    int p = nodes[a].first_euler, q = nodes[b].first_euler;
    if (p > q) {
        std::swap(p, q);
    }
    int l = log2[q - p + 1];
    int st = rmq[l][p + (1 << l) - 1];
    int dr = rmq[l][q];
    if (nodes[st].level < nodes[dr].level) {
        return st;
    } else {
        return dr;
    }
}

int main() {
    std::ifstream fin("atac.in");
    std::ofstream fout("atac.out");
    int n, m, p;
    int x, y, a, b, c, d;

    fin >> n >> m >> p;
    for (int i = 2; i <= n; i++) {
        int u, v;
        fin >> u >> v;
        nodes[u].children.push_back({i, v});
        nodes[i].children.push_back({u, v});
    }
    fin >> x >> y >> a >> b >> c >> d;

    compute_log2(n);
    dfs_euler(1);

    for (int j = 1; j <= 2 * n - 1; j++) {
        rmq[0][j] = euler[j];
    }
    for (int i = 1; (1 << i) <= 2 * n - 1; i++) {
        for (int j = 1; j <= 2 * n - 1; j++) {
            int st = rmq[i - 1][j - (1 << (i - 1))];
            int dr = rmq[i - 1][j];
            if (nodes[st].level < nodes[dr].level) {
                rmq[i][j] = st;
            } else {
                rmq[i][j] = dr;
            }
        }
    }

    for (int i = m; i > 0; i--) {
        int common = lca(n, x, y);
        // urca de la x la common
        int node = x;
        int z = 100001;
        while (node != common) {
            for (const auto& edge : nodes[node].children) {
                const auto& candidate = nodes[edge.child_id];
                if (candidate.in < nodes[node].in && candidate.out > nodes[node].out) {
                    node = edge.child_id;
                    if (edge.cost < z) {
                        z = edge.cost;
                    }
                    break;
                }
            }
        }
        // urca de la y la common
        node = y;
        while (node != common) {
            for (const auto& edge : nodes[node].children) {
                const auto& candidate = nodes[edge.child_id];
                if (candidate.in < nodes[node].in && candidate.out > nodes[node].out) {
                    node = edge.child_id;
                    if (edge.cost < z) {
                        z = edge.cost;
                    }
                    break;
                }
            }
        }

        int x_prim = (x * a + y * b) % n + 1;
        int y_prim = (y * c + z * d) % n + 1;
        x = x_prim;
        y = y_prim;
        if (i <= p) {
            fout << z << '\n';
        }
    }
    return 0;
}