Submission #914250

#	Time	Username	Problem	Language	Result	Execution time	Memory
914250		VMaksimoski008	Regions (IOI09_regions)	C++14	100 / 100	2766 ms	29920 KiB

regions

#include <bits/stdc++.h>
#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 = 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 p1 = upper_bound(all(by_home[r2]), pii{u.first, 0}) - by_home[r2].begin();
            if(p1 >= by_home[r2].size()) continue;

            int p2 = lower_bound(all(by_home[r2]), pii{u.second, 0}) - by_home[r2].begin();
            p2--;
            if(p2 >= by_home[r2].size() || p2 < 0) continue;
 
            ans += max(0, p2 - p1 + 1);
        }
 
        cout << ans << endl;
    }
    
    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int32_t main()':
regions.cpp:48: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]
   48 |         if(by_home[i].size() <= B) continue;
      |            ~~~~~~~~~~~~~~~~~~^~~~
regions.cpp:57: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]
   57 |         if(by_home[r1].size() > B) {
      |            ~~~~~~~~~~~~~~~~~~~^~~
regions.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             if(p1 >= by_home[r2].size()) continue;
      |                ~~~^~~~~~~~~~~~~~~~~~~~~
regions.cpp:69:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             if(p2 >= by_home[r2].size() || p2 < 0) continue;
      |                ~~~^~~~~~~~~~~~~~~~~~~~~

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