Submission #547775

#	Time	Username	Problem	Language	Result	Execution time	Memory
547775		_martynas	Ball Machine (BOI13_ballmachine)	C++11	7.54 / 100	1101 ms	23484 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];
bool taken[MXN];
int root = -1;
int priority = 0;

void dfs(int u, int h)
{
    sort(all(Adj[u]));
    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;
        }
    }

    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];
        }
    }

    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; 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: 0 / 25
• Subtask 2: 6.428571428571429 / 30
• Subtask 3: 0 / 40
• Subtask 4: 1.1111111111111112 / 5