oj.uz

Submission #1014763

# Submission time Handle Problem Language Result Execution time Memory
1014763 2024-07-05T13:26:06 Z phoenix Ball Machine (BOI13_ballmachine) C++17
100 / 100
 141 ms 26588 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 100100;

int n, q;
vector<int> g[N];
int par[N][17], mn[N];

void precalc(int s, int p) {
    par[s][0] = p;
    for (int i = 1; i < 17; i++) 
        par[s][i] = par[par[s][i - 1]][i - 1];
    mn[s] = s;
    for (int to : g[s]) if (to != p) {
        precalc(to, s);
        mn[s] = min(mn[s], mn[to]);
    }
}


int ord[N], num[N], T;

void numerate(int s) {
    sort(g[s].begin(), g[s].end(), [&](int u, int v) { return mn[u] < mn[v]; });
    for (int to : g[s]) if (to != par[s][0]) {
        numerate(to);
    }
    ord[s] = T;
    num[T] = s;
    T++;
}

int root;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        int p;
        cin >> p;
        if (!p) root = i;
        else g[p].push_back(i);
    }
    precalc(root, 0);
    numerate(root);

    set<int> st;
    bool us[n + 1] = {};
    for (int i = 1; i <= n; i++) 
        st.insert(ord[i]);

    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int k, x;
            cin >> k;
            while (k --> 0) {
                x = num[*st.begin()];
                st.erase(st.begin());
                us[x] = true;
            }
            cout << x << '\n';
        } else {
            int x, d = 0;
            cin >> x;
            for (int i = 16; i >= 0; i--) {
                if (us[par[x][i]]) {
                    x = par[x][i];
                    d += (1 << i);
                }
            }
            us[x] = false;
            st.insert(ord[x]);
            cout << d << '\n';
        }
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:66:26: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |             cout << x << '\n';
      |                          ^~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 68 ms 12152 KB Output is correct
3 Correct 43 ms 12372 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2904 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 5 ms 3276 KB Output is correct
10 Correct 14 ms 4956 KB Output is correct
11 Correct 76 ms 12204 KB Output is correct
12 Correct 44 ms 12372 KB Output is correct
13 Correct 60 ms 12268 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 7256 KB Output is correct
2 Correct 98 ms 21328 KB Output is correct
3 Correct 56 ms 16848 KB Output is correct
4 Correct 42 ms 8540 KB Output is correct
5 Correct 43 ms 8272 KB Output is correct
6 Correct 41 ms 8388 KB Output is correct
7 Correct 37 ms 7508 KB Output is correct
8 Correct 21 ms 7256 KB Output is correct
9 Correct 110 ms 21636 KB Output is correct
10 Correct 98 ms 21328 KB Output is correct
11 Correct 87 ms 21328 KB Output is correct
12 Correct 97 ms 18984 KB Output is correct
13 Correct 81 ms 23892 KB Output is correct
14 Correct 57 ms 16800 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 12368 KB Output is correct
2 Correct 120 ms 19576 KB Output is correct
3 Correct 82 ms 21796 KB Output is correct
4 Correct 85 ms 18004 KB Output is correct
5 Correct 73 ms 17664 KB Output is correct
6 Correct 78 ms 17492 KB Output is correct
7 Correct 77 ms 15940 KB Output is correct
8 Correct 90 ms 21840 KB Output is correct
9 Correct 141 ms 21728 KB Output is correct
10 Correct 123 ms 21384 KB Output is correct
11 Correct 120 ms 21452 KB Output is correct
12 Correct 120 ms 19540 KB Output is correct
13 Correct 128 ms 26588 KB Output is correct
14 Correct 81 ms 16844 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 21844 KB Output is correct
2 Correct 127 ms 19540 KB Output is correct
3 Correct 82 ms 26448 KB Output is correct
4 Correct 109 ms 21912 KB Output is correct
5 Correct 108 ms 21500 KB Output is correct
6 Correct 111 ms 21424 KB Output is correct
7 Correct 109 ms 19540 KB Output is correct
8 Correct 90 ms 26452 KB Output is correct
9 Correct 54 ms 16852 KB Output is correct