oj.uz

Submission #501513

# Submission time Handle Problem Language Result Execution time Memory
501513 2022-01-03T14:56:18 Z Joo Regions (IOI09_regions) C++17
35 / 100
 8000 ms 131076 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;
unordered_map<int, int> ans[MR]; //stores answer for big regions(precompute)
vector<int> lis[MR], G[N], ch[N], big; //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);
        }
    }

    for(int bi : big) ans[re[u]][bi] += cnt[bi];
    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)){
            big.emplace_back(i);
        }
    }

    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 11592 KB Output is correct
2 Correct 7 ms 11592 KB Output is correct
3 Correct 9 ms 11592 KB Output is correct
4 Correct 10 ms 11592 KB Output is correct
5 Correct 14 ms 11720 KB Output is correct
6 Correct 24 ms 11720 KB Output is correct
7 Correct 31 ms 11720 KB Output is correct
8 Correct 33 ms 11848 KB Output is correct
9 Correct 51 ms 12644 KB Output is correct
10 Correct 85 ms 12380 KB Output is correct
11 Correct 119 ms 12816 KB Output is correct
12 Correct 128 ms 13644 KB Output is correct
13 Correct 180 ms 13512 KB Output is correct
14 Correct 178 ms 13896 KB Output is correct
15 Correct 290 ms 19156 KB Output is correct

Subtask #2
20.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1058 ms 18872 KB Output isn't correct
2 Incorrect 1303 ms 18152 KB Output isn't correct
3 Incorrect 2106 ms 22076 KB Output isn't correct
4 Correct 310 ms 14220 KB Output is correct
5 Correct 346 ms 17224 KB Output is correct
6 Incorrect 3714 ms 51536 KB Output isn't correct
7 Incorrect 3767 ms 56792 KB Output isn't correct
8 Execution timed out 8022 ms 106436 KB Time limit exceeded
9 Correct 5289 ms 81440 KB Output is correct
10 Runtime error 240 ms 131076 KB Execution killed with signal 9
11 Runtime error 340 ms 131076 KB Execution killed with signal 9
12 Correct 7743 ms 29656 KB Output is correct
13 Execution timed out 8019 ms 31188 KB Time limit exceeded
14 Execution timed out 8080 ms 53668 KB Time limit exceeded
15 Execution timed out 8009 ms 38836 KB Time limit exceeded
16 Execution timed out 8029 ms 53512 KB Time limit exceeded
17 Execution timed out 8048 ms 74940 KB Time limit exceeded