oj.uz

Submission #501511

# Submission time Handle Problem Language Result Execution time Memory
501511 2022-01-03T14:44:22 Z Joo Regions (IOI09_regions) C++17
25 / 100
 6833 ms 94820 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]

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

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

inline 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 < lis[r1].size() or s < lis[r2].size()){
        if((b < lis[r1].size()) and (s == 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;
}

Compilation message

regions.cpp: In function 'int getans(int, int)':
regions.cpp:65:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     while(b < lis[r1].size() or s < lis[r2].size()){
      |           ~~^~~~~~~~~~~~~~~~
regions.cpp:65:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     while(b < lis[r1].size() or s < lis[r2].size()){
      |                                 ~~^~~~~~~~~~~~~~~~
regions.cpp:66:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         if((b < lis[r1].size()) and (s == lis[r2].size() or tin[lis[r1][b]] < tin[lis[r2][s]])){
      |             ~~^~~~~~~~~~~~~~~~
regions.cpp:66:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         if((b < lis[r1].size()) and (s == lis[r2].size() or tin[lis[r1][b]] < tin[lis[r2][s]])){
      |                                      ~~^~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10844 KB Output is correct
2 Correct 6 ms 10824 KB Output is correct
3 Correct 13 ms 10824 KB Output is correct
4 Correct 12 ms 10824 KB Output is correct
5 Correct 14 ms 10824 KB Output is correct
6 Correct 24 ms 10952 KB Output is correct
7 Correct 36 ms 10956 KB Output is correct
8 Correct 44 ms 11060 KB Output is correct
9 Correct 48 ms 11848 KB Output is correct
10 Correct 84 ms 11652 KB Output is correct
11 Correct 121 ms 11976 KB Output is correct
12 Correct 141 ms 12872 KB Output is correct
13 Correct 185 ms 12700 KB Output is correct
14 Correct 227 ms 13120 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 97 ms 35508 KB Execution killed with signal 11
2 Runtime error 114 ms 34272 KB Execution killed with signal 11
3 Runtime error 117 ms 41980 KB Execution killed with signal 11
4 Correct 286 ms 13444 KB Output is correct
5 Correct 385 ms 16444 KB Output is correct
6 Runtime error 1238 ms 34256 KB Execution killed with signal 11
7 Runtime error 1162 ms 37664 KB Execution killed with signal 11
8 Runtime error 2748 ms 59972 KB Execution killed with signal 11
9 Runtime error 1318 ms 53936 KB Execution killed with signal 11
10 Runtime error 6309 ms 86496 KB Execution killed with signal 11
11 Runtime error 4283 ms 73268 KB Execution killed with signal 11
12 Runtime error 2967 ms 50364 KB Execution killed with signal 11
13 Runtime error 2938 ms 53780 KB Execution killed with signal 11
14 Runtime error 6833 ms 55968 KB Execution killed with signal 11
15 Runtime error 5086 ms 66164 KB Execution killed with signal 11
16 Runtime error 4250 ms 94820 KB Execution killed with signal 11
17 Runtime error 6646 ms 91960 KB Execution killed with signal 11