Submission #755428

#	Time	Username	Problem	Language	Result	Execution time	Memory
755428		drdilyor	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	142 ms	24492 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int inf = 1e9;
const ll infl = 1e18;

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    cin >> n >> q;

    vector<vector<int>> child(n);
    vector par(n, 0);
    int root = -1;
    for (int i = 0; i < n; i++) {
        cin >> par[i];
        par[i]--;
        if (~par[i])
            child[par[i]].push_back(i);
        else root = i;
    }

    vector mn(n, inf);
    auto dfs = [&](auto& dfs, int i) -> void {
        mn[i] = i;
        for (int e : child[i]) {
            dfs(dfs, e);
            mn[i] = min(mn[i], mn[e]);
        }
        sort(child[i].begin(), child[i].end(), [&](auto a, auto b) { return mn[a] < mn[b]; });
    };

    dfs(dfs, root);

    int t = 0;
    vector<int> tout(n), id(n);

    auto dfs_ord = [&](auto& dfs_ord, int i)->void {
        for (int e : child[i]) {
            dfs_ord(dfs_ord, e);
        }
        id[t] = i;
        tout[i] = t++;
    };

    dfs_ord(dfs_ord, root);

    vector jmp(20, vector(n, -1));
    jmp[0] = par;
    for (int j = 1; j < 20; j++) {
        for (int i = 0; i < n; i++) {
            if (jmp[j-1][i] !=-1)
                jmp[j][i] = jmp[j-1][jmp[j-1][i]];
        }
    }

    vector has(n, 0);

    while (q--) {
        int t, k;
        cin >> t >> k;
        if (t == 1) {
            for (int i = 0; i < n; i++) {
                if (has[i]) continue;
                has[i] = 1;
                if (--k == 0) {
                    cout << id[i]+1 << '\n';
                    break;
                }
            }
        } else {
            k--;
            int cnt = 0;
            int i = k;
            for (int j = 19; j >= 0; j--) {
                if (jmp[j][i] != -1 && has[tout[jmp[j][i]]]) {
                    cnt += 1 << j;
                    i = jmp[j][i];
                }
            }
            has[tout[i]] = 0;
            cout << cnt << '\n';
        }
    }


    return 0;
}

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