Submission #547256

#	Time	Username	Problem	Language	Result	Execution time	Memory
547256		Jomnoi	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	176 ms	23912 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(const 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(const int &u) {
    for(auto v : graph[u]) {
        postorder(v);
    }
    timer++;
    st[u] = timer;
    pos[timer] = u;
}

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

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

int query(const int &idx, const int &l, const 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];
        if(parent[i][0] == 0) {
            root = i;
        }
        else {
            graph[parent[i][0]].push_back(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--;
                    idx++;
                }
            }
            cout << pos[idx - 1] << '\n';
        }
        else {
            int x;
            cin >> x;
            int u = x;
            for(int i = 19; i >= 0; i--) {
                if(state[parent[u][i]] == true) {
                    u = parent[u][i];
                }
            }
            state[u] = false;
            update(1, 1, N, st[u], false);

            cout << depth[x] - depth[u] << '\n';   
        }
    }
    return 0;
}

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