oj.uz

Submission #501140

# Submission time Handle Problem Language Result Execution time Memory
501140 2022-01-02T12:54:58 Z Joo Regions (IOI09_regions) C++17
30 / 100
 1155 ms 59344 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+10, MR = 510;

int n, R, Q, sz[N], cnt[MR], re[N], ans[MR][MR];
vector<int> G[N], ch[N];

void dfs1(int u, int p){
    sz[u] = 1;
    for(int v : G[u]){
        dfs1(v, u);
        sz[u] += sz[v];
    }
}

void dfs2(int u, int p, bool keep){
    int bc = -1;
    for(int v : G[u]) if(bc == -1 or sz[v] > sz[bc]) bc = v;

    for(int v : G[u]) if(v != bc) dfs2(v, u, 0);
    if(bc != -1){
        dfs2(bc, u, 1);
        swap(ch[u], ch[bc]);
    }
    ch[u].emplace_back(u);
    cnt[re[u]]++;

    for(int v : G[u]){
        if(v == bc) continue;
        for(int vv : ch[v]){
            cnt[re[vv]]++;
            ch[u].emplace_back(vv);
        }
    }
    for(int i = 1; i <= R; i++) ans[re[u]][i] += cnt[i];

    if(keep == 0){
        for(int v : ch[u]) cnt[re[v]]--;
    }
}

int getans(int r1, int r2){
    return ans[r1][r2];
}

int main(void){
    cin >> n >> R >> Q;
    cin >> re[1];
    for(int i = 2; i <= n; i++){
        int p; cin >> p >> re[i];
        G[p].emplace_back(i);
    }

    dfs1(1, -1);
    dfs2(1, -1, 1);

    while(Q--){
        int r1, r2; cin >> r1 >> r2;
        cout << getans(r1, r2) << endl;
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9672 KB Output is correct
2 Correct 7 ms 9672 KB Output is correct
3 Correct 7 ms 9672 KB Output is correct
4 Correct 8 ms 9672 KB Output is correct
5 Correct 14 ms 9800 KB Output is correct
6 Correct 24 ms 10312 KB Output is correct
7 Correct 32 ms 10056 KB Output is correct
8 Correct 39 ms 10184 KB Output is correct
9 Correct 51 ms 11072 KB Output is correct
10 Correct 82 ms 11136 KB Output is correct
11 Correct 106 ms 11080 KB Output is correct
12 Correct 126 ms 12192 KB Output is correct
13 Correct 129 ms 11828 KB Output is correct
14 Correct 174 ms 11904 KB Output is correct
15 Correct 228 ms 16464 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 737 ms 15804 KB Output is correct
2 Correct 991 ms 15352 KB Output is correct
3 Correct 1155 ms 18636 KB Output is correct
4 Runtime error 33 ms 21632 KB Execution killed with signal 11
5 Runtime error 35 ms 25552 KB Execution killed with signal 11
6 Runtime error 53 ms 23660 KB Execution killed with signal 11
7 Runtime error 53 ms 24772 KB Execution killed with signal 11
8 Runtime error 73 ms 35964 KB Execution killed with signal 11
9 Runtime error 120 ms 32972 KB Execution killed with signal 11
10 Runtime error 152 ms 44236 KB Execution killed with signal 11
11 Runtime error 142 ms 30144 KB Execution killed with signal 11
12 Runtime error 169 ms 34744 KB Execution killed with signal 11
13 Runtime error 148 ms 35696 KB Execution killed with signal 11
14 Runtime error 142 ms 33988 KB Execution killed with signal 11
15 Runtime error 141 ms 43996 KB Execution killed with signal 11
16 Runtime error 154 ms 59344 KB Execution killed with signal 11
17 Runtime error 148 ms 56140 KB Execution killed with signal 11