oj.uz

Submission #914246

# Submission time Handle Problem Language Result Execution time Memory
914246 2024-01-21T12:33:32 Z VMaksimoski008 Regions (IOI09_regions) C++14
100 / 100
 2437 ms 29960 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 2 ms 6744 KB Output is correct
3 Correct 2 ms 6744 KB Output is correct
4 Correct 3 ms 6744 KB Output is correct
5 Correct 6 ms 6744 KB Output is correct
6 Correct 10 ms 6744 KB Output is correct
7 Correct 15 ms 6744 KB Output is correct
8 Correct 18 ms 6744 KB Output is correct
9 Correct 25 ms 7172 KB Output is correct
10 Correct 46 ms 7256 KB Output is correct
11 Correct 62 ms 7312 KB Output is correct
12 Correct 75 ms 7804 KB Output is correct
13 Correct 97 ms 7512 KB Output is correct
14 Correct 163 ms 8304 KB Output is correct
15 Correct 179 ms 9952 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1112 ms 13228 KB Output is correct
2 Correct 1125 ms 11800 KB Output is correct
3 Correct 1944 ms 14968 KB Output is correct
4 Correct 161 ms 8268 KB Output is correct
5 Correct 201 ms 9416 KB Output is correct
6 Correct 340 ms 15536 KB Output is correct
7 Correct 703 ms 14420 KB Output is correct
8 Correct 686 ms 25392 KB Output is correct
9 Correct 1273 ms 14988 KB Output is correct
10 Correct 1955 ms 29960 KB Output is correct
11 Correct 2437 ms 14704 KB Output is correct
12 Correct 683 ms 16428 KB Output is correct
13 Correct 1004 ms 17076 KB Output is correct
14 Correct 1285 ms 18304 KB Output is correct
15 Correct 2021 ms 20384 KB Output is correct
16 Correct 2025 ms 25792 KB Output is correct
17 Correct 1997 ms 26796 KB Output is correct