oj.uz

Submission #501159

# Submission time Handle Problem Language Result Execution time Memory
501159 2022-01-02T13:45:14 Z Joo Regions (IOI09_regions) C++17
65 / 100
 8000 ms 35652 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, 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
            if(lar[r1][j+1].second >= sml[r2][i]) 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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10824 KB Output is correct
2 Correct 7 ms 10828 KB Output is correct
3 Correct 7 ms 11008 KB Output is correct
4 Correct 11 ms 10864 KB Output is correct
5 Correct 15 ms 10824 KB Output is correct
6 Correct 29 ms 11208 KB Output is correct
7 Correct 41 ms 11080 KB Output is correct
8 Correct 44 ms 11080 KB Output is correct
9 Correct 68 ms 12080 KB Output is correct
10 Correct 70 ms 12380 KB Output is correct
11 Correct 139 ms 12264 KB Output is correct
12 Correct 139 ms 13500 KB Output is correct
13 Correct 234 ms 13036 KB Output is correct
14 Correct 194 ms 13024 KB Output is correct
15 Correct 266 ms 17688 KB Output is correct

Subtask #2
50.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1092 ms 17360 KB Output is correct
2 Correct 913 ms 16912 KB Output is correct
3 Correct 1517 ms 20264 KB Output is correct
4 Correct 497 ms 12736 KB Output is correct
5 Correct 592 ms 14784 KB Output is correct
6 Correct 2141 ms 14276 KB Output is correct
7 Correct 2427 ms 15552 KB Output is correct
8 Correct 2846 ms 21596 KB Output is correct
9 Correct 3650 ms 22148 KB Output is correct
10 Execution timed out 8015 ms 27932 KB Time limit exceeded
11 Correct 6026 ms 21828 KB Output is correct
12 Execution timed out 8009 ms 23168 KB Time limit exceeded
13 Execution timed out 8016 ms 23612 KB Time limit exceeded
14 Execution timed out 8045 ms 23352 KB Time limit exceeded
15 Execution timed out 8028 ms 28632 KB Time limit exceeded
16 Execution timed out 8007 ms 35652 KB Time limit exceeded
17 Execution timed out 8073 ms 34392 KB Time limit exceeded