Submission #1317009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317009		aaaaaaaa	Regions (IOI09_regions)	C++20	75 / 100	8047 ms	196608 KiB

regions

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
const int mxN = 2e5 + 10;
const int mxR = 25005;
const int B = 205;
vector<int> adj[mxN], rnode[mxR];
pbds region[mxR];
int r[mxN], st[mxN], en[mxN], id[mxR], ans[B][mxN], tin = -1;
void dfs(int u = 1){
    st[u] = ++tin;
    for(auto it : adj[u]){
        dfs(it);
    }
    en[u] = tin;
}
void dfs2(int par = 0, int x = 1, int u = 1, int cnt = 0){
    ans[par][r[u]] += cnt;
    for(auto it : adj[u]) dfs2(par, x, it, cnt + (r[it] == x));
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    int n, k, q, cnt = 0;
    cin >> n >> k >> q >> r[1];
    for(int i = 2, p; i <= n; ++i){
        cin >> p >> r[i];
        adj[p].push_back(i);
    }
    dfs();
    for(int i = 1; i <= n; ++i){
        region[r[i]].insert(st[i]);
        rnode[r[i]].push_back(i);
    }
    for(int i = 1; i <= k; ++i){
        id[i] = -1;
        if((int) rnode[i].size() >= B){
            id[i] = cnt++;
            dfs2(id[i], i, 1, (r[1] == i));
        }
    }
    while(q--){
        int r1, r2;
        cin >> r1 >> r2;
        if((int) rnode[r1].size() >= B){
            cout << ans[id[r1]][r2] << endl;
        }else{
            int ans = 0;
            for(auto it : rnode[r1]){
                ans += region[r2].order_of_key(en[it] + 1) - region[r2].order_of_key(st[it]);
            }
            cout << ans << endl;
        }
    }
    return 0;
}

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