Submission #547784

#	Time	Username	Problem	Language	Result	Execution time	Memory
547784		_martynas	Ball Machine (BOI13_ballmachine)	C++11	100 / 100	170 ms	25268 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;

#define PB push_back
#define F first
#define S second
#define all(a) (a).begin(), (a).end()

using pii = pair<int, int>;

const int MXN = 1e5+5;
const int MXK = 18;

int n, q;
int P[MXN], H[MXN];
int BL[MXK][MXN];
priority_queue<pii, vector<pii>, greater<pii>> PQ;
vector<int> Adj[MXN];
pii node[MXN];
int mn[MXN];
bool taken[MXN];
int root = -1;
int priority = 0;

void dfsmn(int u)
{
    mn[u] = u;
    for(int v : Adj[u]) {
        dfsmn(v);
        mn[u] = min(mn[u], mn[v]);
    }
}

void dfs(int u, int h)
{
    sort(all(Adj[u]),
    [&](int i, int j)
    {
        return mn[i] < mn[j];
    });
    for(int v : Adj[u]) {
        dfs(v, h+1);
    }
    node[u] = {priority++, u};
    H[u] = h;
    PQ.push(node[u]);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        int p; cin >> p;
        if(p) {
            P[i] = p;
            Adj[p].PB(i);
        }
        else {
            root = i;
            P[i] = i;
        }
    }

    fill(mn, mn+n+1, 2*n);
    dfsmn(root);
    dfs(root, 0);
    for(int k = 0; k < MXK; k++)
    for(int i = 1; i <= n; i++) {
        if(k) {
            BL[k][i] = BL[k-1][BL[k-1][i]];
        }
        else {
            BL[k][i] = P[i];
        }
    }

//    auto pqcopy = PQ;
//    while(!pqcopy.empty()) {
//        cerr << pqcopy.top().S << " ";
//        pqcopy.pop();
//    }
//    cerr << "\n";

    for(int qq = 0; qq < q; qq++) {
        int t, x;
        cin >> t >> x;
        if(t == 1) {
            // add
            int last = -1;
            for(int i = 0; i < x; i++) {
                auto u = PQ.top().S;
                PQ.pop();
                taken[u] = true;
                last = u;
            }
            cout << last << "\n";
        }
        else {
            // remove
            int up = 0;
            for(int k = MXK-1; k >= 0; k--) {
                while(taken[BL[k][x]] && x != root) {

                    up += H[x]-H[BL[k][x]];
                    x = BL[k][x];
                }
            }
            taken[x] = false;
            PQ.push(node[x]);
            cout << up << "\n";
        }
    }

    return 0;
}
/*
8 4
0
1
2
2
3
3
4
6
1 8
2 5
2 7
2 8
*/

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