oj.uz

답안 #1016233

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1016233 2024-07-07T14:37:20 Z socpite Regions (IOI09_regions) C++14
35 / 100
 1852 ms 131072 KB 
#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 5;
const int maxr = 25005;
const int blsz = 460;

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

# 결과 실행 시간 메모리 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 4 ms 6744 KB Output is correct
5 Correct 6 ms 6744 KB Output is correct
6 Correct 13 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 26 ms 7256 KB Output is correct
10 Correct 41 ms 7256 KB Output is correct
11 Correct 70 ms 7512 KB Output is correct
12 Correct 97 ms 8024 KB Output is correct
13 Correct 90 ms 7768 KB Output is correct
14 Correct 129 ms 8280 KB Output is correct
15 Correct 198 ms 11608 KB Output is correct

Subtask #2
20.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 92 ms 131072 KB Execution killed with signal 9
2 Runtime error 89 ms 131072 KB Execution killed with signal 9
3 Runtime error 89 ms 131072 KB Execution killed with signal 9
4 Correct 170 ms 8280 KB Output is correct
5 Correct 266 ms 10328 KB Output is correct
6 Runtime error 82 ms 131072 KB Execution killed with signal 9
7 Runtime error 88 ms 131072 KB Execution killed with signal 9
8 Runtime error 102 ms 131072 KB Execution killed with signal 9
9 Correct 1308 ms 16428 KB Output is correct
10 Runtime error 134 ms 131072 KB Execution killed with signal 9
11 Correct 1852 ms 15476 KB Output is correct
12 Runtime error 144 ms 131072 KB Execution killed with signal 9
13 Runtime error 145 ms 131072 KB Execution killed with signal 9
14 Runtime error 152 ms 131072 KB Execution killed with signal 9
15 Runtime error 151 ms 131072 KB Execution killed with signal 9
16 Runtime error 140 ms 131072 KB Execution killed with signal 9
17 Runtime error 140 ms 131072 KB Execution killed with signal 9