Submission #410816

#	Time	Username	Problem	Language	Result	Execution time	Memory
410816		Victor	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	663 ms	23312 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = b - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;

const int INF = 1'000'000'007;

vii graph[100001];
int pos[100001], cur = 0;
map<int, int> empty_nodes;

int find_lo(int u) {
    int lo = u;
    trav(edge, graph[u]) {
        int w, v;
        tie(w, v) = edge;
        w = find_lo(v);
        edge.first = w;
        lo = min(lo, w);
    }
    sort(all(graph[u]));
    return lo;
}

void add(int u) {
    trav(edge, graph[u]) add(edge.second);
    empty_nodes.emplace(cur, u);
    pos[u] = cur++;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    int n, q, root, p[100001], jmp[17][100001];
    cin >> n >> q;

    rep(i, 1, n + 1) {
        cin >> p[i];
        if (!p[i])
            root = i;
        graph[p[i]].emplace_back(0, i);
    }

    find_lo(root);
    add(0);

    rep(j, 1, n + 1) jmp[0][j] = p[j];
    rep(i, 1, 17) rep(j, 1, n + 1) jmp[i][j] = jmp[i - 1][jmp[i - 1][j]];

    rep(i, 0, q) {
        int query, val;
        cin >> query >> val;
        if (query == 1) {
            int ans;
            rep(j, 0, val) {
                ans = empty_nodes.begin()->second;
                empty_nodes.erase(empty_nodes.begin());
            }
            cout << ans << endl;

        } else {
            int u = val, ans = 0;
            per(j, 0, 17) if (!empty_nodes.count(pos[jmp[j][u]])) {
                u = jmp[j][u];
                ans |= 1 << j;
            }
            cout << ans << endl;
            empty_nodes.emplace(pos[u],u);
        }
    }
    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:77:21: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   77 |             cout << ans << endl;
      |                     ^~~
ballmachine.cpp:62:12: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   62 |     find_lo(root);
      |     ~~~~~~~^~~~~~

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