Submission #914238

#	Time	Username	Problem	Language	Result	Execution time	Memory
914238		VMaksimoski008	Regions (IOI09_regions)	C++17	55 / 100	8090 ms	26268 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, i, r1, r2, ans, L, R, p1, p2, mid;
vector<vector<int> > graph;
vector<vector<pii> > by_home;
int in[maxn], out[maxn], dp[210][25001], 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 = 500;
    graph.resize(n+1);
    by_home.resize(r+1);

    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) {
            ans = 0;

            for(pii &u : by_home[r1]) {
                L=0, R=by_home[r2].size()-1, p1 = 1e9, p2 = 1e9;
 
                while(L <= R) {
                    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) {
                    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:58: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]
   58 |         if(by_home[r1].size() <= B) {
      |            ~~~~~~~~~~~~~~~~~~~^~~~

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