oj.uz

Submission #501157

# Submission time Handle Problem Language Result Execution time Memory
501157 2022-01-02T13:40:24 Z Joo Regions (IOI09_regions) C++17
5 / 100
 687 ms 72308 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5+10, MR = 25010, CASE = 0;

int n, R, Q, sz[N], cnt[MR], re[N], tin[N], tout[N], ti;
vector<int> G[N], ch[N], sml[MR];
vector<vector<int>> ans;
vector<pair<int, int>> lar[MR];

void dfs1(int u, int p){
    sz[u] = 1;
    tin[u] = ++ti;
    for(int v : G[u]){
        dfs1(v, u);
        sz[u] += sz[v];
    }
    tout[u] = ti;
}

void dfs2(int u, int p, 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, u, 0);
    if(bc != -1){
        dfs2(bc, u, 1);
        swap(ch[u], ch[bc]);
    }
    ch[u].emplace_back(u);
    cnt[re[u]]++;

    for(int v : G[u]){
        if(v == bc) continue;
        for(int vv : ch[v]){
            cnt[re[vv]]++;
            ch[u].emplace_back(vv);
        }
    }
    for(int i = 1; i <= R; i++) ans[re[u]][i] += cnt[i];

    if(keep == 0){
        for(int v : ch[u]) cnt[re[v]]--;
    }
}

void chk(stack<int> st, int k){
    // cout << "CHKST : ";
    while(!st.empty()){
        // cout << st.top() << " ";
        assert(k <= st.top());
        st.pop();
    }
    // cout << "\n";
}

int getans(int r1, int r2){
    if(R <= CASE) return ans[r1][r2];

    int res = 0;    
    stack<int> st;
    for(int i = 0, j = -1; i < sml[r2].size(); i++){
        while(!st.empty() and sml[r2][i] > st.top()) st.pop(); //pop
        while(j+1 < lar[r1].size() and lar[r1][j+1].second < sml[r2][i]) j++;

        while(j+1 < lar[r1].size() and sml[r2][i] > lar[r1][j+1].first){ //add
            st.push(lar[r1][j+1].second);
            j++;
        }
        while(!st.empty() and sml[r2][i] > st.top()) st.pop(); //pop

        chk(st, sml[r2][i]);

        res += st.size();
    }
    return res;
}

int main(void){
    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, -1);
    if(R <= CASE){
        ans.resize(R+10, vector<int>(R+10));
        dfs2(1, -1, 1);
    }
    else {
        for(int i = 1; i <= n; i++){
            sml[re[i]].emplace_back(tin[i]);
            lar[re[i]].emplace_back(tin[i], tout[i]);
        }
        for(int i = 1; i <= R; i++){
            sort(sml[i].begin(), sml[i].end());
            sort(lar[i].begin(), lar[i].end());
        }

    }

    while(Q--){
        int r1, r2; cin >> r1 >> r2;
        cout << getans(r1, r2) << endl;
    }

    return 0;
}

Compilation message

regions.cpp: In function 'int getans(int, int)':
regions.cpp:62:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = 0, j = -1; i < sml[r2].size(); i++){
      |                            ~~^~~~~~~~~~~~~~~~
regions.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         while(j+1 < lar[r1].size() and lar[r1][j+1].second < sml[r2][i]) j++;
      |               ~~~~^~~~~~~~~~~~~~~~
regions.cpp:66:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         while(j+1 < lar[r1].size() and sml[r2][i] > lar[r1][j+1].first){ //add
      |               ~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 21832 KB Execution killed with signal 6
2 Correct 6 ms 10824 KB Output is correct
3 Correct 7 ms 10824 KB Output is correct
4 Runtime error 13 ms 21904 KB Execution killed with signal 6
5 Runtime error 13 ms 21960 KB Execution killed with signal 6
6 Correct 27 ms 10952 KB Output is correct
7 Runtime error 20 ms 22236 KB Execution killed with signal 6
8 Runtime error 19 ms 22116 KB Execution killed with signal 6
9 Correct 65 ms 11464 KB Output is correct
10 Runtime error 28 ms 23204 KB Execution killed with signal 6
11 Runtime error 25 ms 23800 KB Execution killed with signal 6
12 Runtime error 26 ms 25100 KB Execution killed with signal 6
13 Runtime error 44 ms 24424 KB Execution killed with signal 6
14 Runtime error 34 ms 25844 KB Execution killed with signal 6
15 Correct 687 ms 16004 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 82 ms 33140 KB Execution killed with signal 6
2 Runtime error 86 ms 30468 KB Execution killed with signal 6
3 Runtime error 83 ms 37672 KB Execution killed with signal 6
4 Runtime error 37 ms 25836 KB Execution killed with signal 6
5 Runtime error 49 ms 30032 KB Execution killed with signal 6
6 Runtime error 61 ms 28824 KB Execution killed with signal 6
7 Runtime error 65 ms 31440 KB Execution killed with signal 6
8 Runtime error 93 ms 43836 KB Execution killed with signal 6
9 Runtime error 143 ms 44652 KB Execution killed with signal 6
10 Runtime error 143 ms 56556 KB Execution killed with signal 6
11 Runtime error 180 ms 44264 KB Execution killed with signal 6
12 Runtime error 203 ms 46696 KB Execution killed with signal 6
13 Runtime error 171 ms 47656 KB Execution killed with signal 6
14 Runtime error 215 ms 47372 KB Execution killed with signal 6
15 Runtime error 188 ms 57848 KB Execution killed with signal 6
16 Runtime error 177 ms 72308 KB Execution killed with signal 6
17 Runtime error 167 ms 69352 KB Execution killed with signal 6