oj.uz

Submission #755428

# Submission time Handle Problem Language Result Execution time Memory
755428 2023-06-10T05:39:38 Z drdilyor Ball Machine (BOI13_ballmachine) C++17
100 / 100
 142 ms 24492 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int inf = 1e9;
const ll infl = 1e18;

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, q;
    cin >> n >> q;

    vector<vector<int>> child(n);
    vector par(n, 0);
    int root = -1;
    for (int i = 0; i < n; i++) {
        cin >> par[i];
        par[i]--;
        if (~par[i])
            child[par[i]].push_back(i);
        else root = i;
    }

    vector mn(n, inf);
    auto dfs = [&](auto& dfs, int i) -> void {
        mn[i] = i;
        for (int e : child[i]) {
            dfs(dfs, e);
            mn[i] = min(mn[i], mn[e]);
        }
        sort(child[i].begin(), child[i].end(), [&](auto a, auto b) { return mn[a] < mn[b]; });
    };

    dfs(dfs, root);

    int t = 0;
    vector<int> tout(n), id(n);

    auto dfs_ord = [&](auto& dfs_ord, int i)->void {
        for (int e : child[i]) {
            dfs_ord(dfs_ord, e);
        }
        id[t] = i;
        tout[i] = t++;
    };

    dfs_ord(dfs_ord, root);

    vector jmp(20, vector(n, -1));
    jmp[0] = par;
    for (int j = 1; j < 20; j++) {
        for (int i = 0; i < n; i++) {
            if (jmp[j-1][i] !=-1)
                jmp[j][i] = jmp[j-1][jmp[j-1][i]];
        }
    }

    vector has(n, 0);

    while (q--) {
        int t, k;
        cin >> t >> k;
        if (t == 1) {
            for (int i = 0; i < n; i++) {
                if (has[i]) continue;
                has[i] = 1;
                if (--k == 0) {
                    cout << id[i]+1 << '\n';
                    break;
                }
            }
        } else {
            k--;
            int cnt = 0;
            int i = k;
            for (int j = 19; j >= 0; j--) {
                if (jmp[j][i] != -1 && has[tout[jmp[j][i]]]) {
                    cnt += 1 << j;
                    i = jmp[j][i];
                }
            }
            has[tout[i]] = 0;
            cout << cnt << '\n';
        }
    }


    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 61 ms 9572 KB Output is correct
3 Correct 43 ms 9728 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 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 852 KB Output is correct
10 Correct 10 ms 2516 KB Output is correct
11 Correct 56 ms 9520 KB Output is correct
12 Correct 42 ms 9780 KB Output is correct
13 Correct 53 ms 9528 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4808 KB Output is correct
2 Correct 88 ms 18520 KB Output is correct
3 Correct 55 ms 13916 KB Output is correct
4 Correct 44 ms 6092 KB Output is correct
5 Correct 32 ms 6184 KB Output is correct
6 Correct 32 ms 5868 KB Output is correct
7 Correct 29 ms 4820 KB Output is correct
8 Correct 22 ms 4692 KB Output is correct
9 Correct 82 ms 18876 KB Output is correct
10 Correct 98 ms 18520 KB Output is correct
11 Correct 83 ms 18508 KB Output is correct
12 Correct 103 ms 16204 KB Output is correct
13 Correct 72 ms 21160 KB Output is correct
14 Correct 57 ms 14000 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 9632 KB Output is correct
2 Correct 105 ms 17128 KB Output is correct
3 Correct 110 ms 19324 KB Output is correct
4 Correct 87 ms 15332 KB Output is correct
5 Correct 73 ms 15004 KB Output is correct
6 Correct 59 ms 14940 KB Output is correct
7 Correct 58 ms 13364 KB Output is correct
8 Correct 76 ms 19276 KB Output is correct
9 Correct 116 ms 19708 KB Output is correct
10 Correct 130 ms 19112 KB Output is correct
11 Correct 128 ms 19112 KB Output is correct
12 Correct 117 ms 17116 KB Output is correct
13 Correct 136 ms 24492 KB Output is correct
14 Correct 68 ms 14012 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 19540 KB Output is correct
2 Correct 142 ms 17036 KB Output is correct
3 Correct 81 ms 23796 KB Output is correct
4 Correct 127 ms 19524 KB Output is correct
5 Correct 93 ms 18676 KB Output is correct
6 Correct 112 ms 18644 KB Output is correct
7 Correct 101 ms 16828 KB Output is correct
8 Correct 68 ms 23804 KB Output is correct
9 Correct 54 ms 14040 KB Output is correct