제출 #976649

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
976649		eysbutno	Regions (IOI09_regions)	C++17	100 / 100	3804 ms	34676 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), tout(n), mp(n);
    vector<vector<int>> comp(r);
    int timer = 0;
    function<void(int)> tour = [&](int u) -> void {
        tin[u] = timer++;
        mp[tin[u]] = u;
        comp[region[u]].push_back(tin[u]);
        for (int v : adj[u]) {
            tour(v);
        }
        tout[u] = timer;
    }; 
    tour(0);
    // Precalculating the answer for parent regions with
    // >= sqrt(n) members.
    const int BLOCK = sqrt(n);
    vector<vector<int>> calc;
    vector<int> region_id(r, -1);
    function<void(int, int, int)> dfs = [&](int u, int parent_region, 
                                            int parent_count) -> void {
        if (region[u] == parent_region) ++parent_count;
        calc[region_id[parent_region]][region[u]] += parent_count;
        for (int v : adj[u]) {
            dfs(v, parent_region, parent_count);
        }
    };
    int current_id = 0;
    for (int i = 0; i < r; i++) {
        if ((int) comp[i].size() >= BLOCK) {
            region_id[i] = current_id++;
            calc.push_back(vector<int>(r));
            dfs(0, i, 0);
        }
    }
    // Answering the queries, either with the precalculated
    // values or by using Euler tour + binary search.
    while (q--) {
        int e1, e2;
        cin >> e1 >> e2;
        --e1, --e2;
        if ((int) comp[e1].size() >= BLOCK) {
            cout << calc[region_id[e1]][e2] << "\n";
        } else {
            int tot = 0;
            for (int u : comp[e1]) {
                tot += lower_bound(begin(comp[e2]), end(comp[e2]), tout[mp[u]])
                     - lower_bound(begin(comp[e2]), end(comp[e2]), tin[mp[u]]);
            }
            cout << tot << "\n";
        }
    }
}

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