Submission #1214818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214818		Braabebo10	Regions (IOI09_regions)	C++20	100 / 100	2731 ms	48064 KiB

regions

#include<bits/stdc++.h>
#define ll int
#define nl "\n"
#define all(v) v.begin(),v.end()
#define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;

int main() {
    baraa
    ll n, m, q;
    cin >> n >> m >> q;
    vector<ll> adj[n + 1], dep(n + 1, 0), tree, in(n + 1), out(n + 1), c(n + 1), col[n + 1], timer[n + 1], tin(2 * n);
    for (ll i = 1; i <= n; i++) {
        if (i > 1) {
            ll x;
            cin >> x;
            adj[x].push_back(i);
        }
        cin >> c[i];
        col[c[i]].push_back(i);
    }
    ll dig = 0;
    function<void(ll)> dfs = [&](ll u) {
        tree.push_back(u);
        in[u] = tree.size() - 1;
        tin[in[u]] = u;
        for (ll v: adj[u])
            dfs(v);
        tree.push_back(u);
        out[u] = tree.size() - 1;
        timer[c[u]].push_back(in[u]);
    };
    dfs(1);
    // for (ll i: tree)cout << i << ' ';
    // cout << nl;
    vector<vector<ll> > pre;
    vector<ll> ids(m, -1);
    function<void(ll, ll, ll)> dfs2 = [&](ll u, ll req, ll cnt) {
        if (c[u] == req)cnt++;
        pre[ids[req]][c[u]] += cnt;
        for (ll v: adj[u])
            dfs2(v, req, cnt);
    };
    ll B = sqrtl(n) + 1;
    for (ll i = 1; i <= m; i++) {
        if (col[i].size() >= B) {
            pre.push_back(vector<ll>(m + 1, 0));
            ids[i] = pre.size() - 1;
            dfs2(1, i, 0);
        }
        sort(all(timer[i]));
    }
    while (q--) {
        ll x, y;
        cin >> x >> y;
        if (col[x].size() >= B)
            cout << pre[ids[x]][y] << endl;
        else {
            ll res = 0;
            // for (ll val: timer[y])cout << val << ' ';
            // cout << nl;
            for (ll u: timer[x])
                res += lower_bound(all(timer[y]), out[tin[u]]) - lower_bound(all(timer[y]), in[tin[u]]);
            cout << res << endl;
        }
    }
    return 0;
}

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