제출 #755464

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
755464		The_Samurai	Ball Machine (BOI13_ballmachine)	C++17	65.79 / 100	1099 ms	15744 KiB

ballmachine

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

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

void dfs1(int u) {
    sub[u] = u;
    for (int v: g[u]) {
        dfs1(v);
        sub[u] = min(sub[u], sub[v]);
    }
}

void dfs2(int u) {
    for (int v: g[u]) {
        dfs2(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);
    sub.assign(n + 1, 0);
    pos.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> par[i];
        g[par[i]].emplace_back(i);
    }
    dfs1(0);
    for (int i = 1; i <= n; i++) {
        sort(g[i].begin(), g[i].end(), [&](int u, int v) {
            return sub[u] < sub[v];
        });
    }
    way.clear();
    dfs2(0);
    set<pair<int, int>> emp;
    for (int i = 0; i < n; i++) {
        emp.insert({i, way[i]});
        pos[way[i]] = i;
    }

    while (q--) {
        int t, x;
        cin >> t >> x;
        if (t == 1) {
            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.push_back(*it);
            }
            for (auto it: del) {
                emp.erase(it);
            }
            cout << last << '\n';
        } else {
            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: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 8.571428571428571 / 40
• Subtask 4: 2.2222222222222223 / 5