oj.uz

Submission #914250

# Submission time Handle Problem Language Result Execution time Memory
914250 2024-01-21T12:41:05 Z VMaksimoski008 Regions (IOI09_regions) C++14
100 / 100
 2766 ms 29920 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 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 5 ms 6744 KB Output is correct
6 Correct 9 ms 6744 KB Output is correct
7 Correct 14 ms 6744 KB Output is correct
8 Correct 14 ms 6744 KB Output is correct
9 Correct 22 ms 7176 KB Output is correct
10 Correct 45 ms 7412 KB Output is correct
11 Correct 66 ms 7532 KB Output is correct
12 Correct 72 ms 7768 KB Output is correct
13 Correct 94 ms 7632 KB Output is correct
14 Correct 157 ms 8308 KB Output is correct
15 Correct 187 ms 9956 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1227 ms 13216 KB Output is correct
2 Correct 1443 ms 12188 KB Output is correct
3 Correct 1902 ms 15228 KB Output is correct
4 Correct 159 ms 8268 KB Output is correct
5 Correct 204 ms 9320 KB Output is correct
6 Correct 351 ms 15528 KB Output is correct
7 Correct 761 ms 14400 KB Output is correct
8 Correct 677 ms 25408 KB Output is correct
9 Correct 1397 ms 14992 KB Output is correct
10 Correct 1834 ms 29920 KB Output is correct
11 Correct 2766 ms 14660 KB Output is correct
12 Correct 894 ms 16748 KB Output is correct
13 Correct 1184 ms 17116 KB Output is correct
14 Correct 1424 ms 18292 KB Output is correct
15 Correct 1985 ms 20340 KB Output is correct
16 Correct 1938 ms 25728 KB Output is correct
17 Correct 1845 ms 26792 KB Output is correct