Submission #1127718

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127718		moonpay	Regions (IOI09_regions)	C++17	0 / 100	509 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 = 30;
    vector<int> indexes(n + r + 1), trr(n + r + 1);
    int it = 0;
    for (int i = 1; i <= r; i++) {
        if (ind[i].size() >= B) {
            indexes[i] = it;
            trr[it] = i;
            it++;
        }
    }

    vector<vector<i64>> total(r + 1, vector<i64>(it, 0));

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

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < it; j++) {
            total[reg[i]][j] += mp[i][j];
        }
    }
    for (int i = 0; i < q; i++) {
        int r1, r2;
        std::cin >> r1 >> r2;
        if (ind[r1].size() >= B) {
            std::cout << total[r2][indexes[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: 0 / 15
• Subtask 2: 0 / 85