oj.uz

답안 #673057

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
673057 2022-12-19T13:45:51 Z JooDdae Regions (IOI09_regions) C++17
2 / 100
 5009 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[x].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
2.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 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 8 ms 6488 KB Output isn't correct
5 Incorrect 11 ms 6480 KB Output isn't correct
6 Correct 23 ms 6664 KB Output is correct
7 Incorrect 28 ms 6720 KB Output isn't correct
8 Incorrect 32 ms 6728 KB Output isn't correct
9 Correct 49 ms 7588 KB Output is correct
10 Incorrect 117 ms 7568 KB Output isn't correct
11 Incorrect 175 ms 8080 KB Output isn't correct
12 Incorrect 177 ms 8900 KB Output isn't correct
13 Incorrect 379 ms 8516 KB Output isn't correct
14 Runtime error 31 ms 27944 KB Execution killed with signal 11
15 Runtime error 83 ms 78888 KB Execution killed with signal 11

Subtask #2
0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5009 ms 73176 KB Output isn't correct
2 Runtime error 1816 ms 127004 KB Execution killed with signal 11
3 Incorrect 2741 ms 110572 KB Output isn't correct
4 Runtime error 29 ms 23496 KB Execution killed with signal 11
5 Runtime error 23 ms 21344 KB Execution killed with signal 11
6 Runtime error 57 ms 45184 KB Execution killed with signal 11
7 Runtime error 77 ms 64244 KB Execution killed with signal 11
8 Runtime error 109 ms 115352 KB Execution killed with signal 11
9 Runtime error 211 ms 131072 KB Execution killed with signal 11
10 Runtime error 140 ms 131072 KB Execution killed with signal 9
11 Runtime error 151 ms 131072 KB Execution killed with signal 9
12 Runtime error 156 ms 131072 KB Execution killed with signal 9
13 Runtime error 138 ms 131072 KB Execution killed with signal 9
14 Runtime error 157 ms 131072 KB Execution killed with signal 9
15 Runtime error 134 ms 131072 KB Execution killed with signal 9
16 Runtime error 129 ms 131072 KB Execution killed with signal 9
17 Runtime error 160 ms 131072 KB Execution killed with signal 9