oj.uz

Submission #1016239

# Submission time Handle Problem Language Result Execution time Memory
1016239 2024-07-07T14:43:02 Z socpite Regions (IOI09_regions) C++14
100 / 100
 3936 ms 32024 KB 
#include<bits/stdc++.h>
using namespace std;
 
const int maxn = 2e5 + 5;
const int maxr = 25005;
const int blsz = 500;
 
int n, r, q;
 
int bigans[blsz][maxr];
int cnt[maxr], bigid[maxr], H[maxn];
 
int bigcnt = 0, tdfs = 0;
 
vector<int> g[maxn];
vector<pair<int, int>> euler[maxr];
 
void dfs(int x){
    tdfs++;
    euler[H[x]].push_back({tdfs, 1});
    cnt[H[x]]++;
    for(auto v: g[x])dfs(v);
    tdfs++;
    euler[H[x]].push_back({tdfs, -1});
}
 
void dfs_calc(int x, int id, int dep){
    if(H[x] == id)dep++;
    else bigans[bigcnt][H[x]] += dep;
    for(auto v: g[x])dfs_calc(v, id, dep);
}
 
int main() {
    cin >> n >> r >> q;
    cin >> H[1];
    for(int i = 2; i <= n; i++){
        int p;
        cin >> p >> H[i];
        g[p].push_back(i);
    }
    dfs(1);
    for(int i = 1; i <= r; i++){
        if(cnt[i] >= blsz){
            bigcnt++;
            assert(bigcnt < blsz);
            bigid[i] = bigcnt;
            dfs_calc(1, i, 0);
        }
    }
    while(q--){
        int r1, r2;
        cin >> r1 >> r2;
        if(cnt[r1] >= blsz)cout << bigans[bigid[r1]][r2] << endl;
        else {
            int ptr1 = 0, ptr2 = 0, dep = 0, ans = 0;
            while(ptr1 < euler[r1].size() && ptr2 < euler[r2].size()){
                if(euler[r1][ptr1].first < euler[r2][ptr2].first){
                    dep += euler[r1][ptr1++].second;
                }
                else {
                    if(euler[r2][ptr2++].second == 1)ans += dep;
                }
            }
            cout << ans << endl;
        }
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:56:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             while(ptr1 < euler[r1].size() && ptr2 < euler[r2].size()){
      |                   ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp:56:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             while(ptr1 < euler[r1].size() && ptr2 < euler[r2].size()){
      |                                              ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 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 6740 KB Output is correct
6 Correct 10 ms 6744 KB Output is correct
7 Correct 16 ms 6744 KB Output is correct
8 Correct 18 ms 6744 KB Output is correct
9 Correct 37 ms 7256 KB Output is correct
10 Correct 43 ms 7256 KB Output is correct
11 Correct 61 ms 7512 KB Output is correct
12 Correct 82 ms 8276 KB Output is correct
13 Correct 97 ms 7768 KB Output is correct
14 Correct 143 ms 8280 KB Output is correct
15 Correct 198 ms 11452 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1482 ms 13572 KB Output is correct
2 Correct 1982 ms 12272 KB Output is correct
3 Correct 1875 ms 15608 KB Output is correct
4 Correct 176 ms 8280 KB Output is correct
5 Correct 265 ms 10328 KB Output is correct
6 Correct 582 ms 11352 KB Output is correct
7 Correct 874 ms 10576 KB Output is correct
8 Correct 741 ms 18256 KB Output is correct
9 Correct 1260 ms 16420 KB Output is correct
10 Correct 1969 ms 21408 KB Output is correct
11 Correct 1917 ms 15472 KB Output is correct
12 Correct 1992 ms 18844 KB Output is correct
13 Correct 2799 ms 19296 KB Output is correct
14 Correct 3936 ms 20700 KB Output is correct
15 Correct 2948 ms 23868 KB Output is correct
16 Correct 3244 ms 30848 KB Output is correct
17 Correct 2800 ms 32024 KB Output is correct