Submission #914246

#	Time	Username	Problem	Language	Result	Execution time	Memory
914246		VMaksimoski008	Regions (IOI09_regions)	C++14	100 / 100	2437 ms	29960 KiB

regions

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
 
const int maxn = 2e5 + 5;
 
int n, r, q, in[maxn], out[maxn], timer = 0, B = 320, curr = 0, dp[320][25001], i, r1, r2, ans;
short home[maxn], id[maxn];
vector<int> graph[maxn];
vector<pii> by_home[25001];
 
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;
    
    cin >> home[1];
 
    for(i=2; i<=n; i++) {
        int p;
        cin >> p >> home[i];
        graph[p].push_back(i);
    }
 
    dfs(1);
 
    for(i=1; i<=n; i++)
        by_home[home[i]].push_back({ in[i], out[i] });

    for(i=1; i<=r; i++) {
        sort(by_home[i].begin(), by_home[i].end());
        if(by_home[i].size() <= B) continue;
        id[i] = curr;
        dfs2(1, i, 0);
        curr++;
    }
 
    while(q--) {
        cin >> r1 >> r2;

        if(by_home[r1].size() > B) {
            cout << dp[id[r1]][r2] << endl;
            continue;
        }
 
        ans = 0;
        for(pii &u : by_home[r1]) {
            int l=0, r=by_home[r2].size()-1;
            int p1 = 1e9, p2 = 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;
            }
            
            l=p1, r=by_home[r2].size()-1;
            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(p1 != 1e9 && p2 != 1e9) ans += (p2 - p1 + 1);
        }
 
        cout << ans << endl;
    }
    
    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int32_t main()':
regions.cpp:47:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |         if(by_home[i].size() <= B) continue;
      |            ~~~~~~~~~~~~~~~~~~^~~~
regions.cpp:56:31: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |         if(by_home[r1].size() > B) {
      |            ~~~~~~~~~~~~~~~~~~~^~~

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