Submission #914236

#	Time	Username	Problem	Language	Result	Execution time	Memory
914236		VMaksimoski008	Regions (IOI09_regions)	C++14	55 / 100	8051 ms	26232 KiB

regions

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const int maxn = 1e5 + 5;

int n, r, q, home[maxn], timer = 0, curr = 1;
vector<vector<int> > graph;
vector<vector<pii> > by_home;
int in[maxn], out[maxn], dp[320][25005], id[maxn];

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;
    int B = static_cast<int>(sqrt(n));
    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(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--) {
        int r1, r2;
        cin >> r1 >> r2;

        if(by_home[r1].size() <= B) {
            int ans = 0;

            for(pii &u : by_home[r1]) {
                int l=0, r=by_home[r2].size()-1, 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;
        } else {
            cout << dp[id[r1]][r2] << endl;
        }
    }

    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'int32_t main()':
regions.cpp:49: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]
   49 |         if(by_home[i].size() <= B) continue;
      |            ~~~~~~~~~~~~~~~~~~^~~~
regions.cpp:59: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]
   59 |         if(by_home[r1].size() <= B) {
      |            ~~~~~~~~~~~~~~~~~~~^~~~

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