oj.uz

Submission #501161

# Submission time Handle Problem Language Result Execution time Memory
501161 2022-01-02T13:47:13 Z Joo Regions (IOI09_regions) C++17
95 / 100
 8000 ms 35660 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 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 26 ms 11284 KB Output is correct
7 Correct 29 ms 11080 KB Output is correct
8 Correct 42 ms 11208 KB Output is correct
9 Correct 71 ms 12084 KB Output is correct
10 Correct 122 ms 12304 KB Output is correct
11 Correct 125 ms 12224 KB Output is correct
12 Correct 182 ms 13488 KB Output is correct
13 Correct 181 ms 12928 KB Output is correct
14 Correct 192 ms 13052 KB Output is correct
15 Correct 260 ms 17692 KB Output is correct

Subtask #2
80.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 860 ms 17332 KB Output is correct
2 Correct 836 ms 16892 KB Output is correct
3 Correct 1220 ms 20284 KB Output is correct
4 Correct 178 ms 12808 KB Output is correct
5 Correct 321 ms 14848 KB Output is correct
6 Correct 881 ms 14272 KB Output is correct
7 Correct 982 ms 15532 KB Output is correct
8 Correct 1027 ms 21644 KB Output is correct
9 Correct 1729 ms 22080 KB Output is correct
10 Correct 2490 ms 27880 KB Output is correct
11 Correct 2350 ms 21824 KB Output is correct
12 Correct 3271 ms 23124 KB Output is correct
13 Correct 4176 ms 23504 KB Output is correct
14 Correct 4837 ms 23556 KB Output is correct
15 Correct 6636 ms 28604 KB Output is correct
16 Execution timed out 8036 ms 35660 KB Time limit exceeded
17 Correct 7644 ms 34240 KB Output is correct