Submission #1127709

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127709		moonpay	Regions (IOI09_regions)	C++17	13 / 100	1308 ms	196608 KiB

regions

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#include <functional>
#include <set>
//18:26
using namespace std;

using i64 = long long;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, r, q;
    std::cin >> n >> r >> q;
    std::vector<std::vector<int> > g(n + 1);
    std::vector<int> reg(n + 1);
    std::cin >> reg[1];
    for (int i = 2; i <= n; i++) {
        int h;
        std::cin >> h;
        std::cin >> reg[i];
        g[h].push_back(i);
    }
    std::vector<std::vector<int> > ind(r + 1);
    for (int i = 1; i <= n; i++) ind[reg[i]].push_back(i);
    std::vector<pair<int, int> > xd(n + 1);
    vector<int> tree;
    int timer = 0;
    std::function<void(int, int)> dfs1 = [&](const int u, const int v) {
        xd[u].first = timer;
        tree.push_back(reg[u]);
        for (auto &d: g[u]) {
            if (d != v) {
                timer++;
                dfs1(d, u);
            }
        }
        xd[u].second = timer;
    };
    dfs1(1, -1);
    std::vector<std::vector<int> > times(r + 1);
    for (int i = 1; i <= n; i++) {
        times[reg[i]].push_back(xd[i].first);
    }
    for (int i = 1; i <= r; i++) {
        sort(times[i].begin(), times[i].end());
    }

    constexpr int B = 200;

    vector<unordered_map<int, i64>> total(n + 1);

    std::vector<std::unordered_map<int, i64> > mp(n + 1);
    std::function<void(int, int)> dfs2 = [&](const int u, const int v) {
        if (ind[u].size() >= B) mp[u][reg[u]]++;
        for (const auto &d: g[u]) {
            if (d != v) {
                for (auto &[x, y]: mp[u]) mp[d][x] += y;
                dfs2(d, u);
            }
        }
    };
    dfs2(1, -1);

    for (int i = 1; i <= n; i++) {
        for (auto &[x, y]: mp[i]) total[reg[i]][x] += y;
    }
    for (int i = 0; i < q; i++) {
        int r1, r2;
        std::cin >> r1 >> r2;
        if (ind[r1].size() >= B) {
            std::cout << total[r2][r1] << "\n";
            cout.flush();
        } else {
            i64 answer = 0;
            for (auto &d: ind[r1]) {
                auto [l, r] = xd[d];
                answer += upper_bound(times[r2].begin(), times[r2].end(), r) - lower_bound(
                    times[r2].begin(), times[r2].end(), l);
            }
            std::cout << answer << '\n';
            cout.flush();
        }
    }
}

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