Submission #1014763

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014763		phoenix	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	141 ms	26588 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;

const int N = 100100;

int n, q;
vector<int> g[N];
int par[N][17], mn[N];

void precalc(int s, int p) {
    par[s][0] = p;
    for (int i = 1; i < 17; i++) 
        par[s][i] = par[par[s][i - 1]][i - 1];
    mn[s] = s;
    for (int to : g[s]) if (to != p) {
        precalc(to, s);
        mn[s] = min(mn[s], mn[to]);
    }
}


int ord[N], num[N], T;

void numerate(int s) {
    sort(g[s].begin(), g[s].end(), [&](int u, int v) { return mn[u] < mn[v]; });
    for (int to : g[s]) if (to != par[s][0]) {
        numerate(to);
    }
    ord[s] = T;
    num[T] = s;
    T++;
}

int root;

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) root = i;
        else g[p].push_back(i);
    }
    precalc(root, 0);
    numerate(root);

    set<int> st;
    bool us[n + 1] = {};
    for (int i = 1; i <= n; i++) 
        st.insert(ord[i]);

    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int k, x;
            cin >> k;
            while (k --> 0) {
                x = num[*st.begin()];
                st.erase(st.begin());
                us[x] = true;
            }
            cout << x << '\n';
        } else {
            int x, d = 0;
            cin >> x;
            for (int i = 16; i >= 0; i--) {
                if (us[par[x][i]]) {
                    x = par[x][i];
                    d += (1 << i);
                }
            }
            us[x] = false;
            st.insert(ord[x]);
            cout << d << '\n';
        }
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:66:26: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |             cout << x << '\n';
      |                          ^~~~

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