Submission #547254

#	Time	Username	Problem	Language	Result	Execution time	Memory
547254		Jomnoi	Ball Machine (BOI13_ballmachine)	C++17	75.90 / 100	1086 ms	22092 KiB

ballmachine

#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

const int MAX_N = 1e5 + 10;

int timer;
vector <int> graph[MAX_N];
int depth[MAX_N], parent[MAX_N][20];
int minimum[MAX_N];
int st[MAX_N], pos[MAX_N];
bool state[MAX_N];
bool tree[4 * MAX_N];

int get_min(int u) {
    minimum[u] = u;
    for(auto v : graph[u]) {
        depth[v] = depth[u] + 1;
        minimum[u] = min(minimum[u], get_min(v));
    }
    return minimum[u];
}

void postorder(int u) {
    for(auto v : graph[u]) {
        postorder(v);
    }
    timer++;
    st[u] = timer;
    pos[timer] = u;
}

int jump(int u, int k) {
    for(int i = 0; i < 20; i++) {
        if(k & (1<<i)) {
            u = parent[u][i];
        }
    }
    return u;
}

void update(int idx, int l, int r, int q, bool v) {
    if(l == r) {
        tree[idx] = v;
        return;
    }

    int mid = (l + r) / 2;
    if(q <= mid) {
        return void(update(idx * 2, l, mid, q, v));
    }
    update(idx * 2 + 1, mid + 1, r, q, v);
    tree[idx] = tree[idx * 2] & tree[idx * 2 + 1];
}

int query(int idx, int l, int r) {
    if(l == r) {
        return l;
    }

    int mid = (l + r) / 2;
    if(tree[idx * 2] == false) {
        return query(idx * 2, l, mid);
    }
    return query(idx * 2 + 1, mid + 1, r);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int N, Q;
    cin >> N >> Q;

    int root = 1;
    for(int i = 1; i <= N; i++) {
        cin >> parent[i][0];
        graph[parent[i][0]].push_back(i);
        if(parent[i][0] == 0) {
            root = i;
        }
    }

    get_min(root);
    for(int i = 1; i <= N; i++) {
        sort(graph[i].begin(), graph[i].end(), [&](const int &a, const int &b) {
            return minimum[a] < minimum[b];
        });
    }

    postorder(root);
    depth[0] = -1;
    for(int j = 1; j < 20; j++) {
        for(int i = 1; i <= N; i++) {
            parent[i][j] = parent[parent[i][j - 1]][j - 1];
        }
    }

    while(Q--) {
        int t, idx;
        cin >> t;
        if(t == 1) {
            int k;
            cin >> k;
            while(k > 0) {
                idx = query(1, 1, N);

                while(k > 0 and state[pos[idx]] == false) {
                    state[pos[idx]] = true;
                    update(1, 1, N, idx, true);
                    k--;
                    if(k > 0) {
                        idx++;
                    }
                }
            }
            cout << pos[idx] << '\n';
        }
        else {
            int x;
            cin >> x;
            int l = 0, r = depth[x], res;
            while(l <= r) {
                int mid = (l + r) / 2;

                if(state[jump(x, mid)] == true) {
                    res = mid;
                    l = mid + 1;
                }
                else {
                    r = mid - 1;
                }
            }
            cout << res << '\n';
            
            idx = jump(x, res);
            state[idx] = false;
            update(1, 1, N, st[idx], false);
        }
    }
    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:132:28: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  132 |             cout << res << '\n';
      |                            ^~~~
ballmachine.cpp:115:33: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  115 |             cout << pos[idx] << '\n';
      |                                 ^~~~

• Subtask 1: 19.23076923076923 / 25
• Subtask 2: 15 / 30
• Subtask 3: 40 / 40
• Subtask 4: 1.6666666666666667 / 5