Submission #914242

#	Time	Username	Problem	Language	Result	Execution time	Memory
914242		VMaksimoski008	Regions (IOI09_regions)	C++14	100 / 100	2980 ms	27724 KiB

regions

#include <bits/stdc++.h>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
 
using namespace std;
using pii = pair<int, int>;
 
const int maxn = 2e5 + 5;
 
int n, r, q, in[maxn], out[maxn], timer = 0, B = 500, curr = 0, dp[210][25005];
short home[maxn], id[maxn];
vector<vector<int> > graph;
vector<vector<pii> > by_home;
 
void dfs(int u) {
    in[u] = timer++;
 
    for(int &v : graph[u])
        dfs(v);
 
    out[u] = timer;
}
 
void dfs2(int u, int R, int cnt) {
    if(home[u] == R) cnt++;
    dp[id[R]][home[u]] += cnt;
    for(int &v : graph[u]) dfs2(v, R, cnt);
}
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> r >> q;
    graph.resize(n+1);
    by_home.resize(r+1);
    
    cin >> home[1];
 
    for(int i=2; i<=n; i++) {
        int p;
        cin >> p >> home[i];
        graph[p].push_back(i);
    }
 
    dfs(1);
 
    for(int i=1; i<=n; i++)
        by_home[home[i]].push_back({ in[i], out[i] });

    for(int i=1; i<=r; i++) {
        sort(all(by_home[i]));
        if(sz(by_home[i]) <= B) continue;
        id[i] = curr;
        dfs2(1, i, 0);
        curr++;
    }
 
    while(q--) {
        int r1, r2, ans = 0;
        cin >> r1 >> r2;

        if(sz(by_home[r1]) > B) {
            cout << dp[id[r1]][r2] << endl;
            continue;
        }
 
        for(pii &u : by_home[r1]) {
            //cout << u.first << " " << u.second << '\n';
            int l=0, r=sz(by_home[r2])-1;
            int p1 = 1e9;
 
            while(l <= r) {
                int mid = (l + r) / 2;
                if(by_home[r2][mid].first > u.first) p1 = mid, r = mid - 1;
                else l = mid + 1;
            }
 
            if(p1 == 1e9) continue;
            
            l=p1, r=sz(by_home[r2])-1;
            int p2 = 1e9;
 
            while(l <= r) {
                int mid = (l + r) / 2;
                if(by_home[r2][mid].first < u.second) p2 = mid, l = mid + 1;
                else r = mid - 1;
            }
 
            if(p2 == 1e9) continue;
 
            ans += (p2 - p1 + 1);
        }
 
        cout << ans << endl;
    }
    
    return 0;
}

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