Submission #1260989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260989		spampots	Regions (IOI09_regions)	C++17	100 / 100	3155 ms	41836 KiB

regions

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, R, Q;
    if (!(cin >> N >> R >> Q)) return 0;

    vector<vector<int>> adj(N);
    vector<int> reg(N);

    // Read employees
    cin >> reg[0];
    reg[0]--;
    vector<vector<int>> nodesInRegion(R);
    nodesInRegion[reg[0]].push_back(0);

    for (int i = 1; i < N; i++) {
        int s, h; cin >> s >> h;
        --s; --h;
        reg[i] = h;
        adj[s].push_back(i);
        nodesInRegion[h].push_back(i);
    }

    // Euler tour
    int timer = 0;
    vector<int> tin(N), tout(N), euler(N);
    function<void(int)> dfs = [&](int u) {
        tin[u] = timer;
        euler[timer] = u;
        ++timer;
        for (int v : adj[u]) dfs(v);
        tout[u] = timer; // half-open interval [tin, tout)
    };
    dfs(0);

    // comp[r] = sorted tins of nodes in region r
    vector<vector<int>> comp(R);
    for (int u = 0; u < N; u++) comp[reg[u]].push_back(tin[u]);
    for (int r = 0; r < R; r++) sort(comp[r].begin(), comp[r].end());

    // Heavy regions
    int B = max(1, (int)sqrt((double)N));
    vector<char> isHeavy(R, 0);
    vector<int> heavyId(R, -1);
    int H = 0;
    for (int r = 0; r < R; r++) {
        if ((int)nodesInRegion[r].size() >= B) {
            isHeavy[r] = 1;
            heavyId[r] = H++;
        }
    }

    // get[id][r2] = answer for (r1 = heavy region with id, r2) 
    vector<vector<long long>> get(H, vector<long long>(R, 0));

    // Linear precompute per heavy r1
    for (int r1 = 0; r1 < R; r1++) if (isHeavy[r1]) {
        int id = heavyId[r1];
        int cnt = 0;
        function<void(int)> walk = [&](int u) {
            // Count heavy-r1 ancestors of u; exclude u itself if it’s in r1
            get[id][reg[u]] += cnt;
            if (reg[u] == r1) ++cnt;
            for (int v : adj[u]) walk(v);
            if (reg[u] == r1) --cnt;
        };
        walk(0);
    }

    // Online queries
    while (Q--) {
        int r1, r2; cin >> r1 >> r2; --r1; --r2;
        long long ans = 0;

        if (isHeavy[r1]) {
            ans = get[heavyId[r1]][r2];
        } else {
            // Sum over ancestors in light region r1
            const auto &vecR2 = comp[r2];
            for (int u : nodesInRegion[r1]) {
                int L = tin[u], Righ = tout[u] - 1;
                ans += (long long)(upper_bound(vecR2.begin(), vecR2.end(), Righ)
                                  - lower_bound(vecR2.begin(), vecR2.end(), L));
            }
        }

        cout << ans << '\n';
        cout.flush(); // IOI interactive note
    }
}

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