oj.uz

Submission #501145

# Submission time Handle Problem Language Result Execution time Memory
501145 2022-01-02T13:21:29 Z Joo Regions (IOI09_regions) C++17
30 / 100
 1298 ms 131076 KB 
#include <bits/stdc++.h>
using namespace std;

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

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){
    cout << "CHKST : ";
    while(!st.empty()){
        cout << 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);

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

int main(void){
    cin >> n >> R >> Q;
    cin >> re[1];
    ans.resize(R+10, vector<int>(R+10));
    for(int i = 2; i <= n; i++){
        int p; cin >> p >> re[i];
        G[p].emplace_back(i);
    }

    dfs1(1, -1);
    if(R <= CASE) 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:61:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i = 0, j = -1; i < sml[r2].size(); i++){
      |                            ~~^~~~~~~~~~~~~~~~
regions.cpp:63: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]
   63 |         while(j+1 < lar[r1].size() and lar[r1][j+1].second < sml[r2][i]) j++;
      |               ~~~~^~~~~~~~~~~~~~~~
regions.cpp:65: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]
   65 |         while(j+1 < lar[r1].size() and sml[r2][i] > lar[r1][j+1].first){ //add
      |               ~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10824 KB Output is correct
2 Correct 5 ms 10824 KB Output is correct
3 Correct 7 ms 10824 KB Output is correct
4 Correct 10 ms 10824 KB Output is correct
5 Correct 13 ms 10824 KB Output is correct
6 Correct 26 ms 11208 KB Output is correct
7 Correct 36 ms 11080 KB Output is correct
8 Correct 31 ms 11080 KB Output is correct
9 Correct 57 ms 12096 KB Output is correct
10 Correct 98 ms 12368 KB Output is correct
11 Correct 124 ms 12164 KB Output is correct
12 Correct 177 ms 13492 KB Output is correct
13 Correct 218 ms 13012 KB Output is correct
14 Correct 203 ms 13056 KB Output is correct
15 Correct 258 ms 17764 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 848 ms 17400 KB Output is correct
2 Correct 993 ms 16860 KB Output is correct
3 Correct 1298 ms 20284 KB Output is correct
4 Incorrect 312 ms 75840 KB Output isn't correct
5 Incorrect 360 ms 113140 KB Output isn't correct
6 Runtime error 52 ms 131076 KB Execution killed with signal 9
7 Runtime error 55 ms 131076 KB Execution killed with signal 9
8 Runtime error 47 ms 131076 KB Execution killed with signal 9
9 Runtime error 51 ms 131076 KB Execution killed with signal 9
10 Runtime error 51 ms 131076 KB Execution killed with signal 9
11 Runtime error 52 ms 131076 KB Execution killed with signal 9
12 Runtime error 52 ms 131076 KB Execution killed with signal 9
13 Runtime error 55 ms 131076 KB Execution killed with signal 9
14 Runtime error 52 ms 131076 KB Execution killed with signal 9
15 Runtime error 52 ms 131076 KB Execution killed with signal 9
16 Runtime error 53 ms 131076 KB Execution killed with signal 9
17 Runtime error 48 ms 131076 KB Execution killed with signal 9