oj.uz

Submission #501508

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

const int N = 2e5+10, BLOCK = 500, 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]; //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);
    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 11592 KB Output is correct
2 Correct 5 ms 11592 KB Output is correct
3 Correct 8 ms 11592 KB Output is correct
4 Correct 10 ms 11592 KB Output is correct
5 Correct 12 ms 11704 KB Output is correct
6 Correct 16 ms 11720 KB Output is correct
7 Correct 28 ms 11720 KB Output is correct
8 Correct 35 ms 11848 KB Output is correct
9 Correct 57 ms 12740 KB Output is correct
10 Correct 86 ms 12436 KB Output is correct
11 Correct 101 ms 12812 KB Output is correct
12 Correct 139 ms 13640 KB Output is correct
13 Correct 100 ms 13512 KB Output is correct
14 Correct 254 ms 13896 KB Output is correct
15 Correct 279 ms 19144 KB Output is correct

Subtask #2
40.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1077 ms 18644 KB Output isn't correct
2 Incorrect 1165 ms 18044 KB Output isn't correct
3 Incorrect 1899 ms 21844 KB Output isn't correct
4 Correct 238 ms 14224 KB Output is correct
5 Correct 346 ms 17352 KB Output is correct
6 Correct 894 ms 16072 KB Output is correct
7 Correct 1276 ms 17596 KB Output is correct
8 Correct 1204 ms 26428 KB Output is correct
9 Correct 1924 ms 24944 KB Output is correct
10 Correct 3015 ms 33976 KB Output is correct
11 Correct 3081 ms 27792 KB Output is correct
12 Incorrect 7754 ms 28740 KB Output isn't correct
13 Execution timed out 8006 ms 30484 KB Time limit exceeded
14 Execution timed out 8037 ms 41620 KB Time limit exceeded
15 Execution timed out 8029 ms 34572 KB Time limit exceeded
16 Execution timed out 8054 ms 49824 KB Time limit exceeded
17 Execution timed out 8042 ms 62284 KB Time limit exceeded