Submission #1150103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150103		qiwejfpsdiaj	Regions (IOI09_regions)	C++20	100 / 100	3338 ms	28364 KiB

regions

#include <iostream>
#include <cmath>
#include <vector>

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

    int N, R, Q;
    std::cin >> N >> R >> Q;

    std::vector<int> H(N);
    std::vector<std::vector<int>> G(N), regions(R);
    std::cin >> H[0];
    regions[--H[0]].push_back(0);
    for (int i = 1; i <= N - 1; i++) {
        int s, h;
        std::cin >> s >> h;
        G[--s].push_back(i);
        H[i] = --h;
        regions[h].push_back(i);
    }

    const int BIG_SIZE = std::sqrt(N);
    std::vector<int> big_region_id(R, -1);
    std::vector<std::vector<int>> big;
    for (int i = 0; i < R; i++) {
        if ((int)regions[i].size() >= BIG_SIZE) {
            big_region_id[i] = big.size();
            big.emplace_back(R);

            auto dfs = [&](auto&& self, int u, int r, int cnt) -> void {
                big.back()[H[u]] += cnt;
                for (int v : G[u])
                    self(self, v, r, cnt + (r == H[v]));
            };

            dfs(dfs, 0, i, i == H[0]);
        }
    }

    std::vector<int> start(N), end(N);
    int time = 0;
    std::vector<std::vector<int>> idx(R);
    auto dfs = [&](auto&& self, int u) -> void {
        start[u] = time;
        idx[H[u]].push_back(time++);
        for (int v : G[u])
            self(self, v);
        end[u] = time;
    };
    dfs(dfs, 0);

    while (Q--) {
        int r1, r2;
        std::cin >> r1 >> r2;
        r1--; r2--;

        int res = 0;
        if ((int)regions[r1].size() >= BIG_SIZE) {
            res = big[big_region_id[r1]][r2];
        } else {
            for (int u : regions[r1])
                res += std::lower_bound(idx[r2].begin(), idx[r2].end(), end[u]) - std::lower_bound(idx[r2].begin(), idx[r2].end(), start[u]);
        }

        std::cout << res << '\n' << std::flush;
    }

    return 0;
}

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