oj.uz

Submission #501158

# Submission time Handle Problem Language Result Execution time Memory
501158 2022-01-02T13:44:42 Z Joo Regions (IOI09_regions) C++17
50 / 100
 8000 ms 35656 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
            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 6 ms 10824 KB Output is correct
3 Correct 8 ms 10824 KB Output is correct
4 Correct 11 ms 10824 KB Output is correct
5 Correct 13 ms 10824 KB Output is correct
6 Correct 33 ms 10944 KB Output is correct
7 Correct 38 ms 10952 KB Output is correct
8 Correct 46 ms 10976 KB Output is correct
9 Correct 66 ms 11464 KB Output is correct
10 Correct 96 ms 11464 KB Output is correct
11 Correct 161 ms 11848 KB Output is correct
12 Correct 181 ms 12468 KB Output is correct
13 Correct 265 ms 12176 KB Output is correct
14 Correct 361 ms 12752 KB Output is correct
15 Correct 674 ms 15936 KB Output is correct

Subtask #2
35.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8047 ms 16456 KB Time limit exceeded
2 Execution timed out 8007 ms 15192 KB Time limit exceeded
3 Execution timed out 8083 ms 18720 KB Time limit exceeded
4 Correct 395 ms 12740 KB Output is correct
5 Correct 599 ms 14816 KB Output is correct
6 Correct 2441 ms 14260 KB Output is correct
7 Correct 2197 ms 15536 KB Output is correct
8 Correct 2623 ms 21648 KB Output is correct
9 Correct 3942 ms 22036 KB Output is correct
10 Execution timed out 8087 ms 27884 KB Time limit exceeded
11 Correct 5666 ms 21908 KB Output is correct
12 Execution timed out 8054 ms 23104 KB Time limit exceeded
13 Execution timed out 8057 ms 23640 KB Time limit exceeded
14 Execution timed out 8077 ms 23448 KB Time limit exceeded
15 Execution timed out 8087 ms 28596 KB Time limit exceeded
16 Execution timed out 8023 ms 35656 KB Time limit exceeded
17 Execution timed out 8048 ms 34388 KB Time limit exceeded