oj.uz

Submission #1014762

# Submission time Handle Problem Language Result Execution time Memory
1014762 2024-07-05T13:25:15 Z phoenix Ball Machine (BOI13_ballmachine) C++17
0 / 100
 300 ms 28756 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);
    for (int i = 1; i <= n; i++)
        cout << ord[i] << ' ';
    cout << '\n';

    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:69:26: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |             cout << x << '\n';
      |                          ^~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2908 KB Output isn't correct
2 Incorrect 214 ms 13624 KB Output isn't correct
3 Incorrect 181 ms 13664 KB Output isn't correct
4 Incorrect 2 ms 2652 KB Output isn't correct
5 Incorrect 1 ms 2652 KB Output isn't correct
6 Incorrect 2 ms 2712 KB Output isn't correct
7 Incorrect 3 ms 2908 KB Output isn't correct
8 Incorrect 3 ms 2908 KB Output isn't correct
9 Incorrect 15 ms 3420 KB Output isn't correct
10 Incorrect 54 ms 5452 KB Output isn't correct
11 Incorrect 220 ms 13720 KB Output isn't correct
12 Incorrect 188 ms 13652 KB Output isn't correct
13 Incorrect 246 ms 13920 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 133 ms 7872 KB Output isn't correct
2 Incorrect 244 ms 23160 KB Output isn't correct
3 Incorrect 216 ms 18688 KB Output isn't correct
4 Incorrect 155 ms 9300 KB Output isn't correct
5 Incorrect 177 ms 9296 KB Output isn't correct
6 Incorrect 145 ms 9236 KB Output isn't correct
7 Incorrect 154 ms 8272 KB Output isn't correct
8 Incorrect 122 ms 7852 KB Output isn't correct
9 Incorrect 285 ms 23636 KB Output isn't correct
10 Incorrect 273 ms 23376 KB Output isn't correct
11 Incorrect 237 ms 23124 KB Output isn't correct
12 Incorrect 270 ms 20776 KB Output isn't correct
13 Incorrect 221 ms 25424 KB Output isn't correct
14 Incorrect 198 ms 18380 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 126 ms 13136 KB Output isn't correct
2 Incorrect 268 ms 21396 KB Output isn't correct
3 Incorrect 180 ms 23124 KB Output isn't correct
4 Incorrect 175 ms 19348 KB Output isn't correct
5 Incorrect 185 ms 19024 KB Output isn't correct
6 Incorrect 176 ms 19024 KB Output isn't correct
7 Incorrect 173 ms 17388 KB Output isn't correct
8 Incorrect 173 ms 23276 KB Output isn't correct
9 Incorrect 295 ms 24104 KB Output isn't correct
10 Incorrect 289 ms 23364 KB Output isn't correct
11 Incorrect 292 ms 23376 KB Output isn't correct
12 Incorrect 284 ms 21460 KB Output isn't correct
13 Incorrect 290 ms 28756 KB Output isn't correct
14 Incorrect 251 ms 18964 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 300 ms 23900 KB Output isn't correct
2 Incorrect 285 ms 21328 KB Output isn't correct
3 Incorrect 227 ms 28240 KB Output isn't correct
4 Incorrect 280 ms 23912 KB Output isn't correct
5 Incorrect 267 ms 23264 KB Output isn't correct
6 Incorrect 271 ms 23376 KB Output isn't correct
7 Incorrect 290 ms 21328 KB Output isn't correct
8 Incorrect 254 ms 28244 KB Output isn't correct
9 Incorrect 195 ms 18528 KB Output isn't correct