Submission #755423

#	Time	Username	Problem	Language	Result	Execution time	Memory
755423		The_Samurai	Ball Machine (BOI13_ballmachine)	C++17	7.54 / 100	1094 ms	17480 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> g;
vector<int> par, way, pos;
vector<bool> ball;

void dfs(int u) {
    for (int v: g[u]) {
        dfs(v);
    }
    way.emplace_back(u);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    g.assign(n + 1, {});
    par.assign(n + 1, 0);
    ball.assign(n + 1, false);
    pos.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> par[i];
        g[par[i]].emplace_back(i);
    }
    way.clear();
    dfs(0);
    // dfs way created
    set<pair<int, int>> emp;
    for (int i = 0; i < n; i++) {
        emp.insert({i, way[i]});
        pos[way[i]] = i;
    }
    int empty = n;

    while (q--) {
        int t, x;
        cin >> t >> x;
        if (t == 1) {
            assert(x <= empty);
            empty -= x;
            int i = 0, last = 0;
            vector<pair<int, int>> del;
            for (auto it = emp.begin(); i < x; i++, it++) {
                last = (*it).second;
                ball[(*it).second] = true;
                del.emplace_back(*it);
            }
            for (auto it: del) {
                emp.erase(it);
            }
            cout << last << '\n';
        } else {
            empty++;
            int cnt = 0;
            while (ball[par[x]]) {
                x = par[x];
                cnt++;
            }
            ball[x] = false;
            emp.insert({pos[x], x});
            cout << cnt << '\n';
        }
    }

    return 0;
}

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