Submission #1172397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172397		VMaksimoski008	Ball Machine (BOI13_ballmachine)	C++20	100 / 100	253 ms	34236 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;

struct fenwick {
    int n;
    vector<int> tree;
    fenwick(int _n) : n(_n+10), tree(n+50) {}

    void update(int p, int v) {
        for(p++; p<n; p+=p&-p) tree[p] += v;
    }

    int query(int p) {
        int ans = 0;
        for(p++; p; p-=p&-p) ans += tree[p];
        return ans;
    }
};

int n, q, up[maxn][20], root, timer=1, in[maxn], id[maxn], out[maxn], mn[maxn];
vector<int> G[maxn], ord;

void dfs(int u) {
    in[u] = timer++;
    for(int i=1; i<20; i++) up[u][i] = up[up[u][i-1]][i-1];
    mn[u] = u;
    for(int v : G[u]) {
        up[v][0] = u;
        dfs(v);
        mn[u] = min(mn[u], mn[v]);
    }
    out[u] = timer++;
}

void dfs2(int u) {
    vector<pair<int, int> > ch;
    for(int v : G[u]) ch.push_back({ mn[v], v });
    sort(ch.begin(), ch.end());
    for(auto [_, v] : ch) dfs2(v);
    ord.push_back(u);
    id[u] = ord.size() - 1;
}

signed main() {
    cin >> n >> q;
    for(int i=1; i<=n; i++) {
        int p; cin >> p;
        if(!p) root = i;
        else G[p].push_back(i);
    }

    dfs(root);
    dfs2(root);

    set<int> st;
    for(int i=0; i<n; i++) st.insert(i);

    fenwick fwt(2*n);
    while(q--) {
        int t, u; cin >> t >> u;

        if(t == 1) {
            int last = 0;
            for(int i=0; i<u; i++) {
                int p = *st.begin();
                st.erase(p);
                last = ord[p];
                fwt.update(in[ord[p]], 1);
                fwt.update(out[ord[p]], -1);
            }
            cout << last << '\n';
        } else {
            cout << fwt.query(in[u]) - 1 << '\n';
            for(int i=19; i>=0; i--) {
                if(!up[u][i]) continue;
                if(fwt.query(in[up[u][i]])) u = up[u][i];
            }
            st.insert(id[u]);
            fwt.update(in[u], -1);
            fwt.update(out[u], 1);
        }
    }
}

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