Submission #522287

#	Time	Username	Problem	Language	Result	Execution time	Memory
522287		ddy888	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	545 ms	33712 KiB

ballmachine

#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long 
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr << " " << to_string(H);debug_out(T...);}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

int N, Q, root, post[100010], cnt = 1, par[100010][20], occ[100010], mn[100010];
vector<int> adj[100010];
priority_queue<pi, vector<pi>, greater<pi> > pq;

void dfs(int x, int p) { 
    par[x][0] = p;
    for (int i = 1; i <= 17; ++i) {
        if (par[x][i - 1] == -1) break;
        par[x][i] = par[par[x][i - 1]][i - 1];
    }
    for (auto i: adj[x]) {
        dfs(i, x);
    }
    post[x] = cnt++;
    pq.push({post[x], x});
}

int kth_ancestor(int x, int k) {
    for (int i = 0; i <= 17; ++i) {
        if (x == -1) return -1;
        if (k & (1 << i)) x = par[x][i];
    }
    return x;
}

void add(int x) {
    int ret = 0;
    for (int i = 0; i < x; ++i) {
        ret = pq.top().si;
        pq.pop();
        occ[ret] = 1;
    }
    cout << ret << '\n';
}   

void remove(int x) {
    int lo = 0, hi = N + 1, up = x;
    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        int node = kth_ancestor(x, mid);
        if (node == -1 || occ[node] == 0) hi = mid;
        else {
            lo = mid;
            up = node;
        }
    }
    cout << lo << '\n';
    occ[up] = 0;
    pq.push({post[up], up});
}   

void getmin(int x) {
    mn[x] = x;
    for (auto i: adj[x]) {
        getmin(i);
        mn[x] = min(mn[x], mn[i]);
    }
}

signed main() {
    fast;
    cin >> N >> Q;
    for (int i = 1; i <= N; ++i) {
        int x; cin >> x;
        if (x == 0) {
            root = i;
            continue;
        }
        adj[x].pb(i);
    }
    getmin(root);
    for (int i = 1; i <= N; ++i) {
        sort(adj[i].begin(), adj[i].end(), [](int x, int y) {
            return mn[x] < mn[y];
        });
    }
    memset(par, -1, sizeof par);
    dfs(root, -1);
    while (Q--) {
        int op, x; cin >> op >> x;
        if (op == 1) add(x); 
        else if (op == 2) remove(x);
    }
    return 0;
}

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