oj.uz

Submission #687365

# Submission time Handle Problem Language Result Execution time Memory
687365 2023-01-26T10:59:45 Z JooDdae Regions (IOI09_regions) C++17
60 / 100
 3697 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+1, 0);
        for(int j=0, k=0;j<=n;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]) {
                int u = rev[x];
                while(u) {
                    int L = in[head[u]], R = in[u]; u = p[head[u]];
                    if(!lb[a].empty()) ans += lb[a][R]-lb[a][L-1];
                    else for(auto y : rv[a]) if(L <= y && y <= R) ans++;
                }
            }
        }

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6352 KB Output is correct
2 Correct 4 ms 6352 KB Output is correct
3 Correct 6 ms 6480 KB Output is correct
4 Correct 8 ms 6480 KB Output is correct
5 Correct 11 ms 6532 KB Output is correct
6 Correct 23 ms 6796 KB Output is correct
7 Correct 34 ms 6684 KB Output is correct
8 Correct 46 ms 6724 KB Output is correct
9 Correct 55 ms 7400 KB Output is correct
10 Correct 79 ms 7548 KB Output is correct
11 Correct 177 ms 7968 KB Output is correct
12 Correct 176 ms 8836 KB Output is correct
13 Correct 409 ms 8496 KB Output is correct
14 Correct 569 ms 14792 KB Output is correct
15 Correct 312 ms 39836 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 1063 ms 73088 KB Output is correct
2 Correct 1181 ms 64612 KB Output is correct
3 Correct 1711 ms 110428 KB Output is correct
4 Correct 237 ms 13180 KB Output is correct
5 Correct 323 ms 12660 KB Output is correct
6 Correct 421 ms 24532 KB Output is correct
7 Correct 664 ms 33120 KB Output is correct
8 Correct 871 ms 61036 KB Output is correct
9 Correct 3697 ms 99784 KB Output is correct
10 Runtime error 127 ms 131072 KB Execution killed with signal 9
11 Runtime error 176 ms 131072 KB Execution killed with signal 9
12 Runtime error 155 ms 131072 KB Execution killed with signal 9
13 Runtime error 141 ms 131072 KB Execution killed with signal 9
14 Runtime error 190 ms 131072 KB Execution killed with signal 9
15 Runtime error 154 ms 131072 KB Execution killed with signal 9
16 Runtime error 129 ms 131072 KB Execution killed with signal 9
17 Runtime error 127 ms 131072 KB Execution killed with signal 9