Cod sursa(job #2892310)

Utilizator ViAlexVisan Alexandru ViAlex Data 21 aprilie 2022 17:58:20
Problema Atac Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.12 kb
#include<iostream>
#include<fstream>
#include<vector>

using namespace std;

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

const int max_nodes = 80000;
const int max_paths = 20;
const int inf = 2e9;

struct edge {
    int next, value;
};

int n, m, p, edge_in[max_nodes], subtree_size[max_nodes], num_paths = 1, path_father_node[max_paths];
int node_path[max_nodes], node_depth[max_nodes], path_depth[max_paths], node_path_index[max_nodes];
int rmq[max_paths][20][max_nodes], lg2[max_nodes];

std::vector<edge> g[max_nodes];
std::vector<int> paths[max_paths];

void dfs(int node, int father = 0) {
    subtree_size[node] = 1;
    for (edge e: g[node]) {
        if (e.next == father)
            continue;
        edge_in[e.next] = e.value;
        node_depth[e.next] = node_depth[node] + 1;
        dfs(e.next, node);
        subtree_size[node] += subtree_size[e.next];
    }
}

void heavypath(int node, int father, int current_path) {
    node_path_index[node] = paths[current_path].size();
    paths[current_path].push_back(node);
    node_path[node] = current_path;

    int next_on_path = -1;
    for (edge e: g[node]) {
        if (e.next == father)
            continue;
        if (next_on_path == -1 || subtree_size[e.next] > subtree_size[next_on_path]) {
            next_on_path = e.next;
        }
    }

    if (next_on_path != -1) {
        heavypath(next_on_path, node, current_path);
    }

    for (edge e: g[node]) {
        if (e.next == father || e.next == next_on_path)
            continue;
        num_paths++;
        path_father_node[num_paths - 1] = node;
        path_depth[num_paths - 1] = path_depth[current_path] + 1;
        heavypath(e.next, node, num_paths - 1);
    }
}

void build_log() {
    lg2[1] = 0;
    for (int i = 2; i < max_nodes; i++) {
        lg2[i] = lg2[i / 2] + 1;
    }
}

void build_rmq(int index) {
    unsigned length = paths[index].size();

    for (int i = 0; i < length; i++) {
        rmq[index][0][i] = edge_in[paths[index][i]];
    }

    for (int i = 1; (1 << i) <= length; i++) {
        int size = 1 << i, prev_size = 1 << (i - 1);
        for (int k = 0; k + size <= length; k++) {
            rmq[index][i][k] = min(rmq[index][i - 1][k], rmq[index][i - 1][k + prev_size]);
        }
    }
}

int query_rmq(int index, int left, int right) {
    if (left > right) {
        swap(left, right);
    }
    int distance = right - left + 1, block = lg2[distance];
    int block_size = 1 << block;
    return min(rmq[index][block][left], rmq[index][block][right - block_size + 1]);
}

int query(int first, int second) {
    int result = inf;
    int first_path = node_path[first];
    int second_path = node_path[second];

    while (first_path != second_path) {
        if (path_depth[first_path] > path_depth[second_path]) {
            result = min(result, query_rmq(first_path, 0, node_path_index[first]));
            first = path_father_node[first_path];
            first_path = node_path[first];
        } else {
            result = min(result, query_rmq(second_path, 0, node_path_index[second]));
            second = path_father_node[second_path];
            second_path = node_path[second];
        }
    }
    if (first != second) {
        if (node_depth[first] > node_depth[second]) {
            swap(first, second);
        }
        result = min(result, query_rmq(first_path, node_path_index[first] + 1, node_path_index[second]));
    }
    if (result == inf)
        return 0;

    return result;
}


void read() {
    in >> n >> m >> p;
    int u, v;
    for (int i = 2; i <= n; i++) {
        in >> u >> v;
        g[u].push_back({i, v});
        g[i].push_back({u, v});
    }
}


void solve() {
    build_log();
    dfs(1, 0);

    num_paths = 1;
    path_father_node[0] = 0;
    heavypath(1, 0, 0);


    for (int i = 0; i < num_paths; i++) {
        build_rmq(i);
    }
    int x, y, a, b, c, d, z;
    in >> x >> y >> a >> b >> c >> d;
    z = query(x, y);

    for (int i = 1; i <= m; i++) {
        if (i >= m - p + 1) {
            out << z << '\n';
        }
        x = (x * a + y * b) % n + 1;
        y = (y * c + z * d) % n + 1;
        z = query(x, y);
    }
}

int main() {
    read();
    solve();

    return 0;
}