oj.uz

Submission #673056

# Submission time Handle Problem Language Result Execution time Memory
673056 2022-12-19T13:43:44 Z JooDdae Regions (IOI09_regions) C++17
0 / 100
 1546 ms 131072 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int B = 1;

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]-lb[b][L-1];
                else for(auto y : rv[b]) if(L <= y && y <= R) ans++;
            }
        } else {
            while(b) {
                int L = in[head[b]], R = in[b];
                if(!lb[b].empty()) ans += lb[b][R]-lb[b][L-1];
                else for(auto y : rv[b]) if(L <= y && y <= R) ans++;
                b = p[head[b]];
            }
        }

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

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6352 KB Output isn't correct
2 Incorrect 3 ms 6468 KB Output isn't correct
3 Incorrect 6 ms 6476 KB Output isn't correct
4 Incorrect 8 ms 6504 KB Output isn't correct
5 Incorrect 12 ms 6612 KB Output isn't correct
6 Incorrect 23 ms 7376 KB Output isn't correct
7 Incorrect 16 ms 7544 KB Output isn't correct
8 Incorrect 39 ms 8276 KB Output isn't correct
9 Incorrect 35 ms 13212 KB Output isn't correct
10 Incorrect 53 ms 24032 KB Output isn't correct
11 Incorrect 92 ms 23900 KB Output isn't correct
12 Incorrect 120 ms 44056 KB Output isn't correct
13 Incorrect 171 ms 40508 KB Output isn't correct
14 Incorrect 166 ms 32824 KB Output isn't correct
15 Incorrect 227 ms 51092 KB Output isn't correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 515 ms 73400 KB Output isn't correct
2 Incorrect 641 ms 82516 KB Output isn't correct
3 Incorrect 1546 ms 110632 KB Output isn't correct
4 Runtime error 100 ms 131072 KB Execution killed with signal 9
5 Runtime error 102 ms 131072 KB Execution killed with signal 9
6 Runtime error 103 ms 131072 KB Execution killed with signal 9
7 Runtime error 117 ms 131072 KB Execution killed with signal 9
8 Runtime error 110 ms 131072 KB Execution killed with signal 9
9 Runtime error 148 ms 131072 KB Execution killed with signal 9
10 Runtime error 124 ms 131072 KB Execution killed with signal 9
11 Runtime error 161 ms 131072 KB Execution killed with signal 9
12 Runtime error 162 ms 131072 KB Execution killed with signal 9
13 Runtime error 150 ms 131072 KB Execution killed with signal 9
14 Runtime error 160 ms 131072 KB Execution killed with signal 9
15 Runtime error 140 ms 131072 KB Execution killed with signal 9
16 Runtime error 133 ms 131072 KB Execution killed with signal 9
17 Runtime error 142 ms 131072 KB Execution killed with signal 9