제출 #525522

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
525522		crap_the_coder	Ball Machine (BOI13_ballmachine)	C++17	20.95 / 100	1101 ms	37500 KiB

ballmachine

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

#define int long long
#define endl '\n'

const int MOD = 1e9 + 7;
const int INF = LLONG_MAX >> 1;

const int LOG = 25;

signed main() {
    ios::sync_with_stdio(false); cin.tie(NULL);

    int n, q; cin >> n >> q;
    vector<int> tree[n+1];
    int par[n+1][LOG], cd[n+1]{};

    for (int i = 1; i <= n; i++) {
        int c; cin >> c; cd[c]++;
        tree[c].push_back(i);
        tree[i].push_back(c);
    }

    set<int> lf;
    for (int i = 1; i <= n; i++)
        if (cd[i] == 0)
            lf.insert(i);

    function<void(int, int)> dfs = [&](int u, int p) {
        par[u][0] = p;
        for (int i = 1; i < LOG; i++)
            par[u][i] = par[par[u][i-1]][i-1];

        for (auto v : tree[u])
            if (v != p)
                dfs(v, u);

    }; dfs(0, 0);

    bool marked[n+1]{};

    // Queries
    while (q--) {
        int t, k; cin >> t >> k;

        if (t == 1) {
            int ans = 0;
            while (k--) {
                marked[ans = *lf.begin()] = true;

                lf.erase(lf.begin());
                if (--cd[par[ans][0]] == 0)
                    lf.insert(par[ans][0]);
            }

            cout << ans << endl;

        } else {
            int r = 0;
            for (int j = LOG-1; j >= 0; j--)
                if (marked[par[k][j]])
                    k = par[k][j], r += (1 << j);

            cout << r << endl;

            marked[k] = false; cd[par[k][0]]++;
            lf.insert(k); lf.erase(par[k][0]);
        }
    }
}

• Subtask 1: 0 / 25
• Subtask 2: 10.714285714285714 / 30
• Subtask 3: 8.571428571428571 / 40
• Subtask 4: 1.6666666666666667 / 5