Submission #815975

#	Time	Username	Problem	Language	Result	Execution time	Memory
815975		QwertyPi	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	230 ms	23736 KiB

ballmachine

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

const int MAXN = 1e5 + 11;
const int LGN = 20;
int anc[LGN][MAXN], p[MAXN], st_min[MAXN], t[MAXN], ord[MAXN], ti = 0;
bool a[MAXN];
vector<int> G[MAXN];

void dfs_prec(int v){
    st_min[v] = v;
    for(auto u : G[v]){
        dfs_prec(u);
        st_min[v] = min(st_min[v], st_min[u]);
    }
}

void dfs_order(int v){
    sort(G[v].begin(), G[v].end(), [](int u, int v){ return st_min[u] < st_min[v]; });
    for(auto u : G[v]){
        dfs_order(u);
    }
    t[v] = ++ti; ord[ti] = v;
}

struct BIT{
    int bit[MAXN];
    void add(int p, int v){ p++; for(int i = p; i < MAXN; i += i & -i) bit[i] += v; }
    int qry(int p){ p++; int r = 0; for(int i = p; i; i -= i & -i) r += bit[i]; return r; }
} bit;

int n, q;

int add(){
    int l, r;
    for(l = 1, r = n; l != r;){
        int mid = (l + r) / 2;
        if(bit.qry(mid) == mid) l = mid + 1;
        else r = mid;
    }
    bit.add(l, 1);
    a[ord[l]] = true;
    return ord[l];
}

int remove(int v){
    int jump = 0;
    for(int j = LGN - 1; j >= 0; j--){
        if(a[anc[j][v]]){
            jump += 1 << j;
            v = anc[j][v];
        }
    }
    bit.add(t[v], -1);
    a[v] = false;
    return jump;
}

int32_t main(){
    cin.tie(0); cout.tie(0)->sync_with_stdio(false);
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> p[i]; anc[0][i] = p[i];
        G[p[i]].push_back(i);
    }
    dfs_prec(0);
    dfs_order(0);
    for(int j = 1; j < LGN; j++){
        for(int i = 1; i <= n; i++){
            anc[j][i] = anc[j - 1][anc[j - 1][i]];
        }
    }

    for(int i = 0; i < q; i++){
        int t, k; cin >> t >> k;
        if(t == 1){
            int last_insert = -1;
            for(int i = 0; i < k; i++){
                last_insert = add();
            }
            cout << last_insert << endl;
        }else{
            int drop_down = remove(k);
            cout << drop_down << endl;
        }
    }
}

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