Submission #830012

#	Time	Username	Problem	Language	Result	Execution time	Memory
830012		vjudge1	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	141 ms	24140 KiB

ballmachine

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

/// 123

int32_t main() {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        int n, q;
        cin >> n >> q;
        n++;
        vector<vector<int>> adj(n);
        for (int i = 1; i < n; i++) {
                int p;
                cin >> p;
                adj[p].emplace_back(i);
        }
        int lg = __lg(n);
        vector<vector<int>> up(lg + 1, vector<int>(n, 0));
        vector<int> f(n);
        function<void(int, int)> dfs = [&](int u, int p) {
                up[0][u] = p;
                f[u] = u;
                for (int i = 1; i <= lg; i++) up[i][u] = up[i - 1][up[i - 1][u]];
                for (int v : adj[u]) {
                        dfs(v, u);
                        f[u] = min(f[u], f[v]);
                }
        };
        dfs(0, 0);
        vector<int> ord(n);
        int time = 0;
        function<void(int)> dfso = [&](int u) {
                sort(adj[u].begin(), adj[u].end(), [&](int i, int j) {
                        return f[i] < f[j];
                });
                for (int v : adj[u]) {
                        dfso(v);
                }
                ord[u] = time++;
        };
        dfso(0);
        auto cmp = [&](int i, int j) {
                return ord[i] > ord[j];
        };
        priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);
        for (int i = 0; i < n; i++) pq.emplace(i);
        vector<int> ball(n, 0);
        while (q--) {
                int _, k;
                cin >> _ >> k;
                if (_ == 1) {
                        int res = 0;
                        while (k--) {
                                res = pq.top();
                                pq.pop();
                                ball[res] ^= 1;
                        }
                        cout << res << '\n';
                } else {
                        ball[k] ^= 1;
                        int u = k, res = 0;
                        for (int i = lg; i >= 0; i--) {
                                if (ball[up[i][u]]) u = up[i][u], res += 1 << i;
                        }
                        ball[k] ^= 1;
                        ball[u] ^= 1;
                        pq.emplace(u);
                        cout << res << '\n';
                }
        }
}

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