oj.uz

Submission #1016235

# Submission time Handle Problem Language Result Execution time Memory
1016235 2024-07-07T14:39:28 Z socpite Regions (IOI09_regions) C++17
45 / 100
 1977 ms 131072 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(x, 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++;
            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 'void dfs_calc(int, int, int)':
regions.cpp:30:14: warning: unused variable 'v' [-Wunused-variable]
   30 |     for(auto v: g[x])dfs_calc(x, id, dep);
      |              ^
regions.cpp: In function 'int main()':
regions.cpp:55: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]
   55 |             while(ptr1 < euler[r1].size() && ptr2 < euler[r2].size()){
      |                   ~~~~~^~~~~~~~~~~~~~~~~~
regions.cpp:55: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]
   55 |             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 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 4 ms 6744 KB Output is correct
6 Correct 14 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 23 ms 7256 KB Output is correct
10 Correct 53 ms 7256 KB Output is correct
11 Correct 65 ms 7512 KB Output is correct
12 Correct 73 ms 8024 KB Output is correct
13 Correct 84 ms 7768 KB Output is correct
14 Correct 126 ms 8280 KB Output is correct
15 Correct 179 ms 11504 KB Output is correct

Subtask #2
30.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 82 ms 131072 KB Execution killed with signal 9
2 Runtime error 86 ms 131072 KB Execution killed with signal 9
3 Runtime error 95 ms 131072 KB Execution killed with signal 9
4 Correct 172 ms 8280 KB Output is correct
5 Correct 243 ms 10328 KB Output is correct
6 Runtime error 79 ms 131072 KB Execution killed with signal 9
7 Correct 802 ms 10320 KB Output is correct
8 Runtime error 99 ms 131072 KB Execution killed with signal 9
9 Correct 1305 ms 16432 KB Output is correct
10 Correct 1977 ms 21408 KB Output is correct
11 Correct 1850 ms 15472 KB Output is correct
12 Runtime error 144 ms 131072 KB Execution killed with signal 9
13 Runtime error 141 ms 131072 KB Execution killed with signal 9
14 Runtime error 171 ms 131072 KB Execution killed with signal 9
15 Runtime error 142 ms 131072 KB Execution killed with signal 9
16 Runtime error 147 ms 131072 KB Execution killed with signal 9
17 Runtime error 184 ms 131072 KB Execution killed with signal 9