oj.uz

Submission #673060

# Submission time Handle Problem Language Result Execution time Memory
673060 2022-12-19T13:48:50 Z JooDdae Regions (IOI09_regions) C++17
2 / 100
 3653 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 {
            for(auto x : rv[b]) {
                while(x) {
                    int L = in[head[x]], R = in[x];
                    if(!lb[a].empty()) ans += lb[a][R+1]-lb[a][L];
                    else for(auto y : rv[a]) if(L <= y && y <= R) ans++;
                    x = p[head[x]];
                }
            }
        }

        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
2.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6352 KB Output isn't correct
2 Incorrect 4 ms 6352 KB Output isn't correct
3 Incorrect 4 ms 6476 KB Output isn't correct
4 Incorrect 9 ms 6480 KB Output isn't correct
5 Incorrect 10 ms 6480 KB Output isn't correct
6 Correct 21 ms 6620 KB Output is correct
7 Incorrect 24 ms 6636 KB Output isn't correct
8 Incorrect 37 ms 6772 KB Output isn't correct
9 Correct 50 ms 7412 KB Output is correct
10 Incorrect 116 ms 7544 KB Output isn't correct
11 Incorrect 184 ms 8200 KB Output isn't correct
12 Incorrect 222 ms 8760 KB Output isn't correct
13 Incorrect 447 ms 8524 KB Output isn't correct
14 Incorrect 690 ms 14572 KB Output isn't correct
15 Incorrect 348 ms 39944 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 1065 ms 73108 KB Output isn't correct
2 Incorrect 1253 ms 64412 KB Output isn't correct
3 Incorrect 1396 ms 110420 KB Output isn't correct
4 Incorrect 340 ms 13216 KB Output isn't correct
5 Incorrect 372 ms 12740 KB Output isn't correct
6 Incorrect 435 ms 24540 KB Output isn't correct
7 Incorrect 894 ms 32948 KB Output isn't correct
8 Incorrect 916 ms 61080 KB Output isn't correct
9 Incorrect 3653 ms 99856 KB Output isn't correct
10 Runtime error 144 ms 131072 KB Execution killed with signal 9
11 Runtime error 146 ms 131072 KB Execution killed with signal 9
12 Runtime error 172 ms 131072 KB Execution killed with signal 9
13 Runtime error 175 ms 131072 KB Execution killed with signal 9
14 Runtime error 156 ms 131072 KB Execution killed with signal 9
15 Runtime error 136 ms 131072 KB Execution killed with signal 9
16 Runtime error 130 ms 131072 KB Execution killed with signal 9
17 Runtime error 135 ms 131072 KB Execution killed with signal 9