제출 #1271725

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271725		orzorzorz	Regions (IOI09_regions)	C++20	100 / 100	3007 ms	35160 KiB

regions

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, r, q;
    cin >> n >> r >> q;
    vector<int> region(n);
    cin >> region[0];
    region[0]--;
    vector<vector<int>> adj(n);
    for (int i = 1; i < n; i++) {
        int p, h;
        cin >> p >> h;
        p--, h--;
        adj[p].push_back(i);
        region[i] = h;
    }

    // Calculating Euler tour indices.
    vector<int> tin(n);
    vector<int> tout(n);
    vector<int> tin_node(n);  // tin[tin_node[i]] = i
    vector<vector<int>> comp(r);
    int timer = 0;
    function<void(int)> tour = [&](int u) -> void {
        tin[u] = timer++;
        tin_node[tin[u]] = u;
        comp[region[u]].push_back(tin[u]);
        for (int v : adj[u]) tour(v);
        tout[u] = timer;
    };
    tour(0);

    // Precalculating answers for parent regions with >= sqrt(n) members.
    const int BLOCK = sqrt(n);
    vector<vector<int>> calc(r);  // calc[i][j] = answer for (i,j) if i is heavy

    function<void(int, int, int)> dfs = [&](int u, int parent_region,
                                            int parent_count) -> void {
        if (region[u] == parent_region) parent_count++;
        calc[parent_region][region[u]] += parent_count;
        for (int v : adj[u]) dfs(v, parent_region, parent_count);
    };

    for (int i = 0; i < r; i++) {
        if ((int)comp[i].size() >= BLOCK) {
            calc[i].assign(r, 0);
            dfs(0, i, 0);
        }
    }

    // Answering the queries
    for (int i = 0; i < q; i++) {
        int e1, e2;
        cin >> e1 >> e2;
        e1--, e2--;
        if ((int)comp[e1].size() >= BLOCK) {
            cout << calc[e1][e2] << "\n";
        } else {
            int total = 0;
            for (int u : comp[e1]) {
                total += lower_bound(begin(comp[e2]), end(comp[e2]), tout[tin_node[u]]) -
                         lower_bound(begin(comp[e2]), end(comp[e2]), tin[tin_node[u]]);
            }
            cout << total << '\n';
        }
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 85 / 85