oj.uz

Submission #673059

# Submission time Handle Problem Language Result Execution time Memory
673059 2022-12-19T13:48:19 Z JooDdae Regions (IOI09_regions) C++17
2 / 100
 3947 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 3 ms 6352 KB Output isn't correct
2 Incorrect 4 ms 6408 KB Output isn't correct
3 Incorrect 6 ms 6476 KB Output isn't correct
4 Incorrect 6 ms 6480 KB Output isn't correct
5 Incorrect 12 ms 6532 KB Output isn't correct
6 Correct 15 ms 6668 KB Output is correct
7 Incorrect 22 ms 6672 KB Output isn't correct
8 Incorrect 38 ms 6748 KB Output isn't correct
9 Correct 46 ms 7412 KB Output is correct
10 Incorrect 107 ms 7528 KB Output isn't correct
11 Incorrect 199 ms 8056 KB Output isn't correct
12 Incorrect 176 ms 8868 KB Output isn't correct
13 Incorrect 393 ms 8560 KB Output isn't correct
14 Incorrect 657 ms 14668 KB Output isn't correct
15 Incorrect 253 ms 39964 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 894 ms 73120 KB Output isn't correct
2 Incorrect 1105 ms 64380 KB Output isn't correct
3 Incorrect 1521 ms 110488 KB Output isn't correct
4 Incorrect 282 ms 13244 KB Output isn't correct
5 Incorrect 444 ms 12692 KB Output isn't correct
6 Incorrect 403 ms 24356 KB Output isn't correct
7 Incorrect 794 ms 33064 KB Output isn't correct
8 Incorrect 956 ms 60984 KB Output isn't correct
9 Incorrect 3947 ms 99876 KB Output isn't correct
10 Runtime error 125 ms 131072 KB Execution killed with signal 9
11 Runtime error 145 ms 131072 KB Execution killed with signal 9
12 Runtime error 170 ms 131072 KB Execution killed with signal 9
13 Runtime error 155 ms 131072 KB Execution killed with signal 9
14 Runtime error 156 ms 131072 KB Execution killed with signal 9
15 Runtime error 155 ms 131072 KB Execution killed with signal 9
16 Runtime error 156 ms 131072 KB Execution killed with signal 9
17 Runtime error 142 ms 131072 KB Execution killed with signal 9