oj.uz

Submission #673055

# Submission time Handle Problem Language Result Execution time Memory
673055 2022-12-19T13:42:40 Z JooDdae Regions (IOI09_regions) C++17
0 / 100
 2079 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int B = 160;

int n, r, q, h[200200], p[200200];
int sz[200200], in[200200], out[200200], cnt, lev[200200], head[200200], rev[200200];

vector<int> v[200200], rv[30030], lb[30030];

int dfs_size(int u) {
    for(auto &x : v[u]) {
        sz[u] += dfs_size(x);
        if(sz[x] > sz[v[u][0]]) swap(x, v[u][0]);
    }
    return ++sz[u];
}

void dfs_hld(int u) {
    in[u] = ++cnt, lev[u] = lev[p[u]]+1;
    for(auto x : v[u]) {
        head[x] = (x == v[u][0] ? head[u] : x);
        dfs_hld(x);
    }
    out[u] = cnt;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> r >> q >> h[1];
    for(int i=2;i<=n;i++) cin >> p[i] >> h[i];
    
    for(int i=1;i<=n;i++) v[p[i]].push_back(i);
    head[1] = 1, dfs_size(1), dfs_hld(1);
    for(int i=1;i<=n;i++) rv[h[i]].push_back(in[i]), rev[in[i]] = i;
    for(int i=1;i<=r;i++) sort(rv[i].begin(), rv[i].end());

    for(int i=1;i<=r;i++) if(rv[i].size() >= B) {
        lb[i].resize(n+2, 0);
        for(int j=1, k=0;j<=n+1;j++) {
            while(k < rv[i].size() && rv[i][k] <= j) k++;
            lb[i][j] = k;
        }
    }

    map<pair<int, int>, int> mp;
    while(q--) {
        int a, b; cin >> a >> b;


        if(mp.count({a, b})) { cout << mp[{a, b}] << endl; continue; }

        auto &ans = mp[{a, b}];
        if(rv[a].size() <= rv[b].size()) {
            for(auto x : rv[a]) {
                int L = x, R = out[rev[x]];
                if(!lb[b].empty()) ans += lb[b][R+1]-lb[b][L];
                else for(auto y : rv[b]) if(L <= y && y <= R) ans++;
            }
        } else {
            while(b) {
                int L = in[head[b]], R = in[b];
                if(!lb[b].empty()) ans += lb[b][R+1]-lb[b][L];
                else for(auto y : rv[b]) if(L <= y && y <= R) ans++;
                b = p[head[b]];
            }
        }

        cout << ans << endl;
    }
}

Compilation message

regions.cpp: In function 'int main()':
regions.cpp:42:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             while(k < rv[i].size() && rv[i][k] <= j) k++;
      |                   ~~^~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6352 KB Output isn't correct
2 Incorrect 4 ms 6352 KB Output isn't correct
3 Incorrect 5 ms 6480 KB Output isn't correct
4 Incorrect 8 ms 6488 KB Output isn't correct
5 Incorrect 7 ms 6532 KB Output isn't correct
6 Incorrect 20 ms 6676 KB Output isn't correct
7 Incorrect 34 ms 6680 KB Output isn't correct
8 Incorrect 31 ms 6712 KB Output isn't correct
9 Incorrect 45 ms 7292 KB Output isn't correct
10 Incorrect 81 ms 7564 KB Output isn't correct
11 Incorrect 120 ms 8060 KB Output isn't correct
12 Incorrect 135 ms 8812 KB Output isn't correct
13 Incorrect 187 ms 8460 KB Output isn't correct
14 Incorrect 242 ms 14636 KB Output isn't correct
15 Incorrect 222 ms 39892 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 834 ms 73024 KB Output isn't correct
2 Incorrect 769 ms 64412 KB Output isn't correct
3 Incorrect 1543 ms 110556 KB Output isn't correct
4 Incorrect 284 ms 13120 KB Output isn't correct
5 Incorrect 363 ms 12744 KB Output isn't correct
6 Incorrect 275 ms 24404 KB Output isn't correct
7 Incorrect 840 ms 32968 KB Output isn't correct
8 Incorrect 815 ms 60956 KB Output isn't correct
9 Incorrect 2079 ms 99788 KB Output isn't correct
10 Runtime error 135 ms 131072 KB Execution killed with signal 9
11 Runtime error 164 ms 131072 KB Execution killed with signal 9
12 Runtime error 172 ms 131072 KB Execution killed with signal 9
13 Runtime error 149 ms 131072 KB Execution killed with signal 9
14 Runtime error 163 ms 131072 KB Execution killed with signal 9
15 Runtime error 154 ms 131072 KB Execution killed with signal 9
16 Runtime error 134 ms 131072 KB Execution killed with signal 9
17 Runtime error 140 ms 131072 KB Execution killed with signal 9