oj.uz

Submission #501166

# Submission time Handle Problem Language Result Execution time Memory
501166 2022-01-02T13:51:22 Z Joo Regions (IOI09_regions) C++17
30 / 100
 4523 ms 35608 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 6 ms 10824 KB Output is correct
2 Correct 6 ms 10824 KB Output is correct
3 Correct 7 ms 10824 KB Output is correct
4 Correct 10 ms 10884 KB Output is correct
5 Correct 11 ms 10952 KB Output is correct
6 Correct 13 ms 11208 KB Output is correct
7 Correct 35 ms 11080 KB Output is correct
8 Correct 41 ms 11236 KB Output is correct
9 Correct 48 ms 12104 KB Output is correct
10 Correct 109 ms 12264 KB Output is correct
11 Correct 96 ms 12268 KB Output is correct
12 Correct 182 ms 13520 KB Output is correct
13 Correct 178 ms 12976 KB Output is correct
14 Correct 201 ms 13140 KB Output is correct
15 Correct 267 ms 17772 KB Output is correct

Subtask #2
15.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 646 ms 17392 KB Output is correct
2 Correct 955 ms 16904 KB Output is correct
3 Correct 1294 ms 20212 KB Output is correct
4 Incorrect 283 ms 12852 KB Output isn't correct
5 Incorrect 330 ms 14792 KB Output isn't correct
6 Incorrect 683 ms 14280 KB Output isn't correct
7 Incorrect 1008 ms 15552 KB Output isn't correct
8 Incorrect 922 ms 21696 KB Output isn't correct
9 Incorrect 1538 ms 22176 KB Output isn't correct
10 Incorrect 1986 ms 27944 KB Output isn't correct
11 Incorrect 2182 ms 21940 KB Output isn't correct
12 Incorrect 2326 ms 23200 KB Output isn't correct
13 Incorrect 2216 ms 23652 KB Output isn't correct
14 Incorrect 3095 ms 23520 KB Output isn't correct
15 Incorrect 4081 ms 28736 KB Output isn't correct
16 Incorrect 4445 ms 35608 KB Output isn't correct
17 Incorrect 4523 ms 34368 KB Output isn't correct