oj.uz

Submission #673062

# Submission time Handle Problem Language Result Execution time Memory
673062 2022-12-19T13:52:28 Z JooDdae Regions (IOI09_regions) C++17
3 / 100
 4088 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=0, 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]-lb[b][L-1];
                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]-lb[a][L-1];
                    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
3.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 6 ms 6480 KB Output isn't correct
4 Incorrect 9 ms 6480 KB Output isn't correct
5 Incorrect 12 ms 6480 KB Output isn't correct
6 Correct 17 ms 6620 KB Output is correct
7 Incorrect 34 ms 6700 KB Output isn't correct
8 Incorrect 43 ms 6784 KB Output isn't correct
9 Correct 55 ms 7392 KB Output is correct
10 Incorrect 98 ms 7604 KB Output isn't correct
11 Incorrect 188 ms 8004 KB Output isn't correct
12 Incorrect 185 ms 8768 KB Output isn't correct
13 Incorrect 317 ms 8464 KB Output isn't correct
14 Incorrect 648 ms 14652 KB Output isn't correct
15 Correct 255 ms 39948 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 763 ms 73092 KB Output isn't correct
2 Incorrect 949 ms 64484 KB Output isn't correct
3 Incorrect 1448 ms 110524 KB Output isn't correct
4 Incorrect 205 ms 13244 KB Output isn't correct
5 Incorrect 321 ms 12844 KB Output isn't correct
6 Incorrect 502 ms 24432 KB Output isn't correct
7 Incorrect 859 ms 32924 KB Output isn't correct
8 Incorrect 661 ms 60968 KB Output isn't correct
9 Incorrect 4088 ms 99876 KB Output isn't correct
10 Runtime error 132 ms 131072 KB Execution killed with signal 9
11 Runtime error 150 ms 131072 KB Execution killed with signal 9
12 Runtime error 158 ms 131072 KB Execution killed with signal 9
13 Runtime error 158 ms 131072 KB Execution killed with signal 9
14 Runtime error 160 ms 131072 KB Execution killed with signal 9
15 Runtime error 139 ms 131072 KB Execution killed with signal 9
16 Runtime error 128 ms 131072 KB Execution killed with signal 9
17 Runtime error 129 ms 131072 KB Execution killed with signal 9