oj.uz

Submission #501510

# Submission time Handle Problem Language Result Execution time Memory
501510 2022-01-03T14:44:07 Z Joo Regions (IOI09_regions) C++17
40 / 100
 1384 ms 131076 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+10, BLOCK = -1, 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 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 9 ms 10824 KB Output is correct
5 Correct 18 ms 11004 KB Output is correct
6 Correct 32 ms 11208 KB Output is correct
7 Correct 20 ms 11080 KB Output is correct
8 Correct 20 ms 11264 KB Output is correct
9 Correct 60 ms 12176 KB Output is correct
10 Correct 118 ms 12364 KB Output is correct
11 Correct 123 ms 12336 KB Output is correct
12 Correct 208 ms 13696 KB Output is correct
13 Correct 181 ms 13116 KB Output is correct
14 Correct 174 ms 13268 KB Output is correct
15 Correct 257 ms 18584 KB Output is correct

Subtask #2
25.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 823 ms 17992 KB Output is correct
2 Correct 1036 ms 17340 KB Output is correct
3 Correct 1260 ms 21220 KB Output is correct
4 Correct 978 ms 76184 KB Output is correct
5 Correct 1384 ms 114576 KB Output is correct
6 Runtime error 73 ms 131076 KB Execution killed with signal 9
7 Runtime error 73 ms 131076 KB Execution killed with signal 9
8 Runtime error 77 ms 131076 KB Execution killed with signal 9
9 Runtime error 96 ms 131076 KB Execution killed with signal 9
10 Runtime error 109 ms 131076 KB Execution killed with signal 9
11 Runtime error 118 ms 131076 KB Execution killed with signal 9
12 Runtime error 168 ms 131076 KB Execution killed with signal 9
13 Runtime error 148 ms 131076 KB Execution killed with signal 9
14 Runtime error 125 ms 131076 KB Execution killed with signal 9
15 Runtime error 116 ms 131076 KB Execution killed with signal 9
16 Runtime error 112 ms 131076 KB Execution killed with signal 9
17 Runtime error 129 ms 131072 KB Execution killed with signal 9