oj.uz

Submission #501169

# Submission time Handle Problem Language Result Execution time Memory
501169 2022-01-02T13:53:23 Z Joo Regions (IOI09_regions) C++17
100 / 100
 4451 ms 35676 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, st[N];
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, idx = 0;    
    for(int i = 0, j = -1; i < sml[r2].size(); i++){
        while(idx > 0 and sml[r2][i] > st[idx]) idx--; //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[++idx] = lar[r1][j+1].second;
            j++;
        }

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

        res += idx;
    }
    return res;
}

int main(void){
    ios_base::sync_with_stdio(0); cin.tie(0);
    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: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 5 ms 10824 KB Output is correct
2 Correct 6 ms 10824 KB Output is correct
3 Correct 7 ms 10856 KB Output is correct
4 Correct 10 ms 10824 KB Output is correct
5 Correct 13 ms 10952 KB Output is correct
6 Correct 24 ms 11208 KB Output is correct
7 Correct 36 ms 11080 KB Output is correct
8 Correct 28 ms 11208 KB Output is correct
9 Correct 46 ms 12096 KB Output is correct
10 Correct 108 ms 12280 KB Output is correct
11 Correct 130 ms 12248 KB Output is correct
12 Correct 179 ms 13628 KB Output is correct
13 Correct 117 ms 13084 KB Output is correct
14 Correct 196 ms 13128 KB Output is correct
15 Correct 208 ms 17704 KB Output is correct

Subtask #2
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 833 ms 17428 KB Output is correct
2 Correct 915 ms 16960 KB Output is correct
3 Correct 1319 ms 20272 KB Output is correct
4 Correct 251 ms 12872 KB Output is correct
5 Correct 240 ms 14828 KB Output is correct
6 Correct 675 ms 14244 KB Output is correct
7 Correct 976 ms 15528 KB Output is correct
8 Correct 891 ms 21696 KB Output is correct
9 Correct 1422 ms 22176 KB Output is correct
10 Correct 2130 ms 27912 KB Output is correct
11 Correct 2133 ms 21944 KB Output is correct
12 Correct 1831 ms 23188 KB Output is correct
13 Correct 2529 ms 23644 KB Output is correct
14 Correct 2863 ms 23508 KB Output is correct
15 Correct 4038 ms 28684 KB Output is correct
16 Correct 4173 ms 35676 KB Output is correct
17 Correct 4451 ms 34372 KB Output is correct