oj.uz

Submission #830012

# Submission time Handle Problem Language Result Execution time Memory
830012 2023-08-18T17:33:44 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 141 ms 24140 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 316 KB Output is correct
2 Correct 72 ms 8820 KB Output is correct
3 Correct 48 ms 9108 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 12 ms 2380 KB Output is correct
11 Correct 67 ms 8852 KB Output is correct
12 Correct 45 ms 9032 KB Output is correct
13 Correct 60 ms 8864 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4752 KB Output is correct
2 Correct 111 ms 17916 KB Output is correct
3 Correct 58 ms 12688 KB Output is correct
4 Correct 35 ms 5580 KB Output is correct
5 Correct 36 ms 5516 KB Output is correct
6 Correct 35 ms 5460 KB Output is correct
7 Correct 35 ms 4468 KB Output is correct
8 Correct 22 ms 4820 KB Output is correct
9 Correct 99 ms 18320 KB Output is correct
10 Correct 106 ms 17988 KB Output is correct
11 Correct 95 ms 17964 KB Output is correct
12 Correct 100 ms 15280 KB Output is correct
13 Correct 77 ms 21360 KB Output is correct
14 Correct 58 ms 12600 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 9224 KB Output is correct
2 Correct 114 ms 15888 KB Output is correct
3 Correct 88 ms 19252 KB Output is correct
4 Correct 74 ms 14744 KB Output is correct
5 Correct 77 ms 14480 KB Output is correct
6 Correct 72 ms 14392 KB Output is correct
7 Correct 73 ms 12536 KB Output is correct
8 Correct 91 ms 19244 KB Output is correct
9 Correct 109 ms 18528 KB Output is correct
10 Correct 119 ms 18064 KB Output is correct
11 Correct 114 ms 18128 KB Output is correct
12 Correct 119 ms 15940 KB Output is correct
13 Correct 141 ms 24140 KB Output is correct
14 Correct 78 ms 12660 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 18648 KB Output is correct
2 Correct 122 ms 15908 KB Output is correct
3 Correct 90 ms 24080 KB Output is correct
4 Correct 124 ms 18628 KB Output is correct
5 Correct 122 ms 18116 KB Output is correct
6 Correct 105 ms 18160 KB Output is correct
7 Correct 118 ms 15744 KB Output is correct
8 Correct 88 ms 24004 KB Output is correct
9 Correct 59 ms 12644 KB Output is correct