oj.uz

Submission #501512

# Submission time Handle Problem Language Result Execution time Memory
501512 2022-01-03T14:49:16 Z Joo Regions (IOI09_regions) C++17
25 / 100
 6902 ms 94592 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+10, BLOCK = 300, MR = 25010;

int n, R, Q, tin[N], tout[N], sz[N], re[N], cnt[MR], ti;
vector<int> ans[MR]; //stores answer for big regions(precompute)
vector<int> lis[MR], G[N], ch[N]; //lis[i] denotes a list of those whose region is i sorted by tin[i]

void add(int p, int u){
    ch[p].emplace_back(u);
    cnt[re[u]]++;
}

bool isbig(int r){
    return ((int)lis[r].size() > BLOCK);
}

bool isAnc(int p, int u){
    return (tin[p] <= tin[u] and tout[u] <= tout[p]);
}

void dfs1(int u){
    sz[u] = 1;
    lis[re[u]].emplace_back(u);

    tin[u] = ++ti;
    for(int v : G[u]) dfs1(v), sz[u] += sz[v];
    tout[u] = ti;
}

void dfs2(int u, 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, 0);
    if(bc != -1){
        dfs2(bc, 1);
        swap(ch[bc], ch[u]);
    }
    
    add(u, u);
    for(int v : G[u]){
        if(v == bc) continue;
        for(int vv : ch[v]){
            add(u, vv);
        }
    }

    if(isbig(re[u])){
        for(int r = 1; r <= R; r++){
            ans[re[u]][r] += cnt[r];
        }
    }

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

}

int getans(int r1, int r2){
    int b = 0, s = 0, res = 0;
    stack<int> st;
    while(b < (int)lis[r1].size() or s < (int)lis[r2].size()){
        if((b < (int)lis[r1].size()) and (s == (int)lis[r2].size() or tin[lis[r1][b]] < tin[lis[r2][s]])){
            while(!st.empty() and !isAnc(st.top(), lis[r1][b])) st.pop();
            st.push(lis[r1][b]);

            b++;
        } else {
            while(!st.empty() and !isAnc(st.top(), lis[r2][s])) st.pop();

            res += st.size();
            s++;
        }
    }
    return res;
}

int main(void){
    ios_base::sync_with_stdio(0); cin.tie(0);
    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);

    for(int i = 1; i <= R; i++){
        if(isbig(i)) ans[i].resize(R+10);
    }

    dfs2(1, 1);

    while(Q--){
        int r1, r2; cin >> r1 >> r2;
        if(isbig(r1) or isbig(r2)){
            cout << ans[r1][r2] << endl;
        } else {
            cout << getans(r1, r2) << endl;
        }
    }

    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10824 KB Output is correct
2 Correct 6 ms 10824 KB Output is correct
3 Correct 7 ms 10824 KB Output is correct
4 Correct 10 ms 10824 KB Output is correct
5 Correct 13 ms 10824 KB Output is correct
6 Correct 25 ms 10952 KB Output is correct
7 Correct 37 ms 10916 KB Output is correct
8 Correct 41 ms 11056 KB Output is correct
9 Correct 56 ms 11848 KB Output is correct
10 Correct 86 ms 11652 KB Output is correct
11 Correct 109 ms 12036 KB Output is correct
12 Correct 143 ms 12876 KB Output is correct
13 Correct 187 ms 12632 KB Output is correct
14 Correct 226 ms 13076 KB Output is correct
15 Correct 254 ms 18376 KB Output is correct

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 88 ms 35632 KB Execution killed with signal 11
2 Runtime error 103 ms 34304 KB Execution killed with signal 11
3 Runtime error 108 ms 41884 KB Execution killed with signal 11
4 Correct 278 ms 13440 KB Output is correct
5 Correct 349 ms 16456 KB Output is correct
6 Runtime error 1262 ms 34160 KB Execution killed with signal 11
7 Runtime error 1224 ms 37360 KB Execution killed with signal 11
8 Runtime error 2824 ms 59836 KB Execution killed with signal 11
9 Runtime error 1379 ms 53780 KB Execution killed with signal 11
10 Runtime error 6547 ms 86288 KB Execution killed with signal 11
11 Runtime error 4432 ms 73124 KB Execution killed with signal 11
12 Runtime error 3034 ms 50304 KB Execution killed with signal 11
13 Runtime error 3031 ms 53608 KB Execution killed with signal 11
14 Runtime error 6902 ms 56144 KB Execution killed with signal 11
15 Runtime error 5210 ms 66204 KB Execution killed with signal 11
16 Runtime error 4295 ms 94592 KB Execution killed with signal 11
17 Runtime error 6729 ms 91776 KB Execution killed with signal 11