oj.uz

답안 #908479

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
908479 2024-01-16T12:46:51 Z anarch_y Regions (IOI09_regions) C++17
30 / 100
 2281 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
#define pb push_back

const int maxn = 200001;
vector<int> adj[maxn];
int home[maxn];
map<int, int> mp[maxn];
map<pair<int, int>, int> ans;

void dfs(int s, int p){
    mp[s][home[s]] = 1;
    for(auto u: adj[s]){
        if(u == p) continue;
        dfs(u, s);
        if(sz(mp[s]) < sz(mp[u])) swap(mp[u], mp[s]);
        for(auto &[r, m]: mp[u]) mp[s][r] += m; 
    }
    for(auto &[r, m]: mp[s]){
        if(r == home[s]){
            ans[{r, r}] += m-1;
        }
        else{
            ans[{home[s], r}] += m;
        }
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, R, Q; cin >> N >> R >> Q;
    int h; cin >> h; home[1] = h;
    for(int i=2; i<=N; i++){
        int p, g; cin >> p >> g;
        adj[i].pb(p); adj[p].pb(i);
        home[i] = g; 
    }
    dfs(1, 0);

    while(Q--){
        int r1, r2; cin >> r1 >> r2;
        cout << ans[{r1, r2}] << "\n";
        cout.flush();
    }
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 15192 KB Output is correct
2 Correct 4 ms 15444 KB Output is correct
3 Correct 5 ms 15348 KB Output is correct
4 Correct 7 ms 15636 KB Output is correct
5 Correct 10 ms 15340 KB Output is correct
6 Correct 30 ms 19012 KB Output is correct
7 Correct 26 ms 16804 KB Output is correct
8 Correct 31 ms 18640 KB Output is correct
9 Correct 148 ms 21964 KB Output is correct
10 Correct 94 ms 25868 KB Output is correct
11 Correct 146 ms 21992 KB Output is correct
12 Correct 572 ms 30276 KB Output is correct
13 Correct 140 ms 25396 KB Output is correct
14 Correct 164 ms 22364 KB Output is correct
15 Correct 850 ms 27056 KB Output is correct

Subtask #2
15.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1130 ms 26904 KB Output is correct
2 Correct 750 ms 29164 KB Output is correct
3 Correct 2281 ms 31624 KB Output is correct
4 Runtime error 550 ms 131072 KB Execution killed with signal 9
5 Runtime error 667 ms 131072 KB Execution killed with signal 9
6 Runtime error 576 ms 131072 KB Execution killed with signal 9
7 Runtime error 468 ms 131072 KB Execution killed with signal 9
8 Runtime error 675 ms 131072 KB Execution killed with signal 9
9 Runtime error 459 ms 131072 KB Execution killed with signal 9
10 Runtime error 760 ms 131072 KB Execution killed with signal 9
11 Runtime error 523 ms 131072 KB Execution killed with signal 9
12 Runtime error 729 ms 131072 KB Execution killed with signal 9
13 Runtime error 632 ms 131072 KB Execution killed with signal 9
14 Runtime error 629 ms 131072 KB Execution killed with signal 9
15 Runtime error 515 ms 131072 KB Execution killed with signal 9
16 Runtime error 404 ms 131072 KB Execution killed with signal 9
17 Runtime error 539 ms 131072 KB Execution killed with signal 9