Submission #88561

#	Time	Username	Problem	Language	Result	Execution time	Memory
88561		wolfris	Ball Machine (BOI13_ballmachine)	C++14	16.11 / 100	372 ms	23492 KiB

ballmachine

#include <iostream>
#include <algorithm>
#include <math.h>
#include <queue>
#include <vector>
 
using namespace std;
 
int n, q, root, p[20][100015], h[100015];
vector <int> a[100015];
int c[100015], id[100015], node[100015], maxId;
priority_queue <int, vector <int>, greater <int>> heap;
bool ball[100015];
 
void dfs(int u) {
    c[u] = u;
    for (int v: a[u])
        h[v] = h[u] + 1,
        dfs(v), c[u] = min(c[u], c[v]);
}
 
bool cmp(int u, int v) {
    return c[u] < c[v];
}
 
void assignId(int u) {
    sort(a[u].begin(), a[u].end());
    for (int v: a[u]) assignId(v);
    id[u] = ++maxId; node[maxId] = u;
    heap.push(maxId);
}
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int u = 1; u <= n; ++u) {
        cin >> p[0][u];
        if (p[0][u])
            a[p[0][u]].push_back(u);
        else root = u;
    }
    h[root] = 1; dfs(root); assignId(root);
    for (int i = 1; (1 << i) <= n; ++i)
        for (int u = 1; u <= n; ++u)
            p[i][u] = p[i - 1][p[i - 1][u]];
    for (int cmd, k; q--;) {
        cin >> cmd >> k;
        if (cmd == 1) {
            int u;
            while (k--)
                u = node[heap.top()],
                ball[u] = true, heap.pop();
            cout << u << '\n';
        }
        else {
            int u = k;
            for (int i = log2(h[u]); i >= 0; --i)
                if (ball[p[i][u]]) u = p[i][u];
            ball[u] = false; heap.push(id[u]);
            cout << h[k] - h[u] << '\n';
        }
    }
}

Compilation message (stderr)

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

• Subtask 1: 0 / 25
• Subtask 2: 6.428571428571429 / 30
• Subtask 3: 8.571428571428571 / 40
• Subtask 4: 1.1111111111111112 / 5