oj.uz

답안 #883303

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
883303 2023-12-05T05:58:08 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 187 ms 29216 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 100'000;

int n, q, root;
int cntRank, rnk[N + 10], subMin[N + 10], revRank[N + 10];
int par[N + 10], h[N + 10], sz[N + 10];
int tim, st[N + 10], head[N + 10], revSt[N + 10];
vector<int> adj[N + 10];
vector<pair<int, int>> adj2[N + 10];

void readInput() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> par[i];
        if (par[i])
            adj[par[i]].push_back(i);
        else
            root = i;
    }
}

void init(int u = root) {
    h[u] = h[par[u]] + 1;
    sz[u] = 1;
    subMin[u] = u;
    for (auto v: adj[u]) {
        init(v);
        sz[u] += sz[v];
        subMin[u] = min(subMin[u], subMin[v]);
        adj2[u].push_back({subMin[v], v});
    }
    sort(adj2[u].begin(), adj2[u].end());
}

void calcRank(int u = root) {
    for (auto [x, v]: adj2[u])
        calcRank(v);
    rnk[u] = ++cntRank;
    revRank[cntRank] = u;
}

void hld(int u = root, int hed = 0) {
    head[u] = (hed? hed: u);
    st[u] = ++tim;
    revSt[tim] = u;
    int bigChild = 0;
    for (auto v: adj[u])
        if (sz[v] > sz[bigChild])
            bigChild = v;
    if (bigChild)
        hld(bigChild, head[u]);
    for (auto v: adj[u])
        if (v != bigChild)
            hld(v, 0);
}

int mn[2][4 * N + 10];

int get(int st, int en, int t, int id = 1, int l = 1, int r = n + 1) {
    if (en <= l || r <= st || mn[t][id])
        return 0;
    if (l + 1 == r)
        return l;
    int mid = (l + r) >> 1;
    int case1 = get(st, en, t, id << 1, l, mid);
    if (case1)
        return case1;
    return get(st, en, t, id << 1 | 1, mid, r);
}

void update(int idx, int val, int t, int id = 1, int l = 1, int r = n + 1) {
    if (idx < l || r <= idx)
        return;
    if (l + 1 == r) {
        mn[t][id] = val;
        return;
    }
    int mid = (l + r) >> 1;
    update(idx, val, t, id << 1, l, mid);
    update(idx, val, t, id << 1 | 1, mid, r);
    mn[t][id] = min(mn[t][id << 1], mn[t][id << 1 | 1]);
}

void build() {
    fill(mn[1] + 1, mn[1] + 4 * n + 10, 1);
}

int lastHave(int u) {
    int res = 0;
    while (u) {
        int tmp = get(st[head[u]], st[u] + 1, 1);
        if (tmp)
            res = tmp;
        u = par[head[u]];
    }
    return revSt[res];
}

void queryDel() {
    int u;
    cin >> u;
    int p = lastHave(u);
    cout << h[u] - h[p] << '\n';
    update(st[p], 1, 1);
    update(rnk[p], 0, 0);
}

void queryAdd() {
    int k;
    cin >> k;
    int ans;
    while (k--) {
        int u = revRank[get(1, n + 1, 0)];
        update(st[u], 0, 1);
        update(rnk[u], 1, 0);
        ans = u;
    }
    cout << ans << '\n';
}

void solve() {
    while (q--) {
        int type;
        cin >> type;
        if (type == 1)
            queryAdd();
        else
            queryDel();
    }
    cout.flush();
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    init();
    calcRank();
    hld();
    build();
    solve();
    return 0;
}

Compilation message

ballmachine.cpp: In function 'void queryAdd()':
ballmachine.cpp:120:20: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  120 |     cout << ans << '\n';
      |                    ^~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 184 ms 14732 KB Output is correct
3 Correct 69 ms 14420 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 3 ms 10724 KB Output is correct
7 Correct 3 ms 10588 KB Output is correct
8 Correct 3 ms 10588 KB Output is correct
9 Correct 11 ms 10844 KB Output is correct
10 Correct 36 ms 11864 KB Output is correct
11 Correct 187 ms 14868 KB Output is correct
12 Correct 67 ms 14604 KB Output is correct
13 Correct 183 ms 14416 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 14416 KB Output is correct
2 Correct 149 ms 21836 KB Output is correct
3 Correct 63 ms 15736 KB Output is correct
4 Correct 94 ms 14772 KB Output is correct
5 Correct 95 ms 14520 KB Output is correct
6 Correct 80 ms 14464 KB Output is correct
7 Correct 85 ms 13664 KB Output is correct
8 Correct 39 ms 14404 KB Output is correct
9 Correct 130 ms 22628 KB Output is correct
10 Correct 150 ms 22096 KB Output is correct
11 Correct 133 ms 21844 KB Output is correct
12 Correct 137 ms 19384 KB Output is correct
13 Correct 94 ms 26584 KB Output is correct
14 Correct 71 ms 15548 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 16720 KB Output is correct
2 Correct 143 ms 19860 KB Output is correct
3 Correct 89 ms 25184 KB Output is correct
4 Correct 105 ms 20240 KB Output is correct
5 Correct 91 ms 19540 KB Output is correct
6 Correct 88 ms 19540 KB Output is correct
7 Correct 100 ms 17672 KB Output is correct
8 Correct 88 ms 25168 KB Output is correct
9 Correct 155 ms 22864 KB Output is correct
10 Correct 140 ms 22100 KB Output is correct
11 Correct 170 ms 22100 KB Output is correct
12 Correct 145 ms 19804 KB Output is correct
13 Correct 157 ms 29216 KB Output is correct
14 Correct 150 ms 16424 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 151 ms 23372 KB Output is correct
2 Correct 154 ms 19792 KB Output is correct
3 Correct 95 ms 28672 KB Output is correct
4 Correct 149 ms 22992 KB Output is correct
5 Correct 168 ms 22040 KB Output is correct
6 Correct 131 ms 22048 KB Output is correct
7 Correct 147 ms 19792 KB Output is correct
8 Correct 122 ms 28780 KB Output is correct
9 Correct 64 ms 15720 KB Output is correct