oj.uz

Submission #673064

# Submission time Handle Problem Language Result Execution time Memory
673064 2022-12-19T13:54:06 Z JooDdae Regions (IOI09_regions) C++17
60 / 100
 3828 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]) {
                x = rev[x];
                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
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6380 KB Output is correct
2 Correct 4 ms 6456 KB Output is correct
3 Correct 6 ms 6480 KB Output is correct
4 Correct 9 ms 6404 KB Output is correct
5 Correct 10 ms 6480 KB Output is correct
6 Correct 23 ms 6620 KB Output is correct
7 Correct 28 ms 6640 KB Output is correct
8 Correct 33 ms 6728 KB Output is correct
9 Correct 60 ms 7416 KB Output is correct
10 Correct 91 ms 7556 KB Output is correct
11 Correct 217 ms 8012 KB Output is correct
12 Correct 172 ms 8808 KB Output is correct
13 Correct 365 ms 8484 KB Output is correct
14 Correct 737 ms 14624 KB Output is correct
15 Correct 250 ms 40004 KB Output is correct

Subtask #2
45.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 890 ms 73028 KB Output is correct
2 Correct 1220 ms 64516 KB Output is correct
3 Correct 1544 ms 110416 KB Output is correct
4 Correct 339 ms 13164 KB Output is correct
5 Correct 418 ms 12732 KB Output is correct
6 Correct 447 ms 24476 KB Output is correct
7 Correct 866 ms 33008 KB Output is correct
8 Correct 1124 ms 61052 KB Output is correct
9 Correct 3828 ms 99820 KB Output is correct
10 Runtime error 150 ms 131072 KB Execution killed with signal 9
11 Runtime error 146 ms 131072 KB Execution killed with signal 9
12 Runtime error 173 ms 131072 KB Execution killed with signal 9
13 Runtime error 139 ms 131072 KB Execution killed with signal 9
14 Runtime error 171 ms 131072 KB Execution killed with signal 9
15 Runtime error 141 ms 131072 KB Execution killed with signal 9
16 Runtime error 122 ms 131072 KB Execution killed with signal 9
17 Runtime error 127 ms 131072 KB Execution killed with signal 9