oj.uz

Submission #501509

# Submission time Handle Problem Language Result Execution time Memory
501509 2022-01-03T14:42:28 Z Joo Regions (IOI09_regions) C++17
65 / 100
 8000 ms 46772 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+10, BLOCK = 2e5+10, 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 7 ms 10784 KB Output is correct
2 Correct 6 ms 10824 KB Output is correct
3 Correct 9 ms 10788 KB Output is correct
4 Correct 11 ms 10824 KB Output is correct
5 Correct 11 ms 10824 KB Output is correct
6 Correct 20 ms 10952 KB Output is correct
7 Correct 33 ms 10952 KB Output is correct
8 Correct 34 ms 10952 KB Output is correct
9 Correct 53 ms 11852 KB Output is correct
10 Correct 65 ms 11652 KB Output is correct
11 Correct 118 ms 11976 KB Output is correct
12 Correct 120 ms 12880 KB Output is correct
13 Correct 147 ms 12660 KB Output is correct
14 Correct 218 ms 13064 KB Output is correct
15 Correct 274 ms 18416 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 6795 ms 17760 KB Output is correct
2 Execution timed out 8073 ms 17136 KB Time limit exceeded
3 Execution timed out 8042 ms 20924 KB Time limit exceeded
4 Correct 292 ms 13384 KB Output is correct
5 Correct 249 ms 16456 KB Output is correct
6 Correct 1050 ms 15296 KB Output is correct
7 Correct 1384 ms 16804 KB Output is correct
8 Correct 1248 ms 25616 KB Output is correct
9 Correct 1946 ms 24252 KB Output is correct
10 Correct 2938 ms 33124 KB Output is correct
11 Correct 3243 ms 27060 KB Output is correct
12 Correct 6964 ms 24928 KB Output is correct
13 Execution timed out 8025 ms 26744 KB Time limit exceeded
14 Execution timed out 8055 ms 26208 KB Time limit exceeded
15 Execution timed out 8006 ms 32732 KB Time limit exceeded
16 Execution timed out 8034 ms 46772 KB Time limit exceeded
17 Execution timed out 8071 ms 43704 KB Time limit exceeded