oj.uz

Submission #673058

# Submission time Handle Problem Language Result Execution time Memory
673058 2022-12-19T13:46:44 Z JooDdae Regions (IOI09_regions) C++17
3 / 100
 3642 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;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 5 ms 6480 KB Output isn't correct
4 Incorrect 8 ms 6500 KB Output isn't correct
5 Incorrect 15 ms 6528 KB Output isn't correct
6 Correct 25 ms 6616 KB Output is correct
7 Incorrect 35 ms 6620 KB Output isn't correct
8 Incorrect 41 ms 6804 KB Output isn't correct
9 Correct 65 ms 7432 KB Output is correct
10 Incorrect 99 ms 7500 KB Output isn't correct
11 Incorrect 181 ms 8052 KB Output isn't correct
12 Incorrect 187 ms 8748 KB Output isn't correct
13 Incorrect 356 ms 8508 KB Output isn't correct
14 Incorrect 686 ms 14608 KB Output isn't correct
15 Correct 290 ms 39848 KB Output is correct

Subtask #2
0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 912 ms 73228 KB Output isn't correct
2 Incorrect 1259 ms 64400 KB Output isn't correct
3 Incorrect 1538 ms 110444 KB Output isn't correct
4 Incorrect 345 ms 13164 KB Output isn't correct
5 Incorrect 428 ms 12908 KB Output isn't correct
6 Incorrect 575 ms 24488 KB Output isn't correct
7 Incorrect 608 ms 33008 KB Output isn't correct
8 Incorrect 989 ms 61164 KB Output isn't correct
9 Incorrect 3642 ms 99836 KB Output isn't correct
10 Runtime error 135 ms 131072 KB Execution killed with signal 9
11 Runtime error 143 ms 131072 KB Execution killed with signal 9
12 Runtime error 170 ms 131072 KB Execution killed with signal 9
13 Runtime error 147 ms 131072 KB Execution killed with signal 9
14 Runtime error 151 ms 131072 KB Execution killed with signal 9
15 Runtime error 137 ms 131072 KB Execution killed with signal 9
16 Runtime error 128 ms 131072 KB Execution killed with signal 9
17 Runtime error 130 ms 131072 KB Execution killed with signal 9