oj.uz

Submission #88562

# Submission time Handle Problem Language Result Execution time Memory
88562 2018-12-06T15:10:32 Z wolfris Ball Machine (BOI13_ballmachine) C++14
100 / 100
 442 ms 23476 KB 
#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(), cmp);
    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

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
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 106 ms 9676 KB Output is correct
3 Correct 61 ms 9892 KB Output is correct
4 Correct 4 ms 9892 KB Output is correct
5 Correct 4 ms 9892 KB Output is correct
6 Correct 5 ms 9892 KB Output is correct
7 Correct 5 ms 9892 KB Output is correct
8 Correct 5 ms 9892 KB Output is correct
9 Correct 9 ms 9892 KB Output is correct
10 Correct 22 ms 9892 KB Output is correct
11 Correct 103 ms 9892 KB Output is correct
12 Correct 60 ms 10008 KB Output is correct
13 Correct 99 ms 10008 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 10008 KB Output is correct
2 Correct 318 ms 17832 KB Output is correct
3 Correct 86 ms 17832 KB Output is correct
4 Correct 86 ms 17832 KB Output is correct
5 Correct 98 ms 17832 KB Output is correct
6 Correct 92 ms 17832 KB Output is correct
7 Correct 85 ms 17832 KB Output is correct
8 Correct 40 ms 17832 KB Output is correct
9 Correct 355 ms 18472 KB Output is correct
10 Correct 387 ms 18472 KB Output is correct
11 Correct 211 ms 18472 KB Output is correct
12 Correct 339 ms 18472 KB Output is correct
13 Correct 125 ms 20892 KB Output is correct
14 Correct 77 ms 20892 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 20892 KB Output is correct
2 Correct 293 ms 20892 KB Output is correct
3 Correct 212 ms 20892 KB Output is correct
4 Correct 137 ms 20892 KB Output is correct
5 Correct 195 ms 20892 KB Output is correct
6 Correct 192 ms 20892 KB Output is correct
7 Correct 193 ms 20892 KB Output is correct
8 Correct 182 ms 20892 KB Output is correct
9 Correct 233 ms 20892 KB Output is correct
10 Correct 442 ms 20892 KB Output is correct
11 Correct 363 ms 20892 KB Output is correct
12 Correct 306 ms 20892 KB Output is correct
13 Correct 320 ms 23476 KB Output is correct
14 Correct 119 ms 23476 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 23476 KB Output is correct
2 Correct 295 ms 23476 KB Output is correct
3 Correct 127 ms 23476 KB Output is correct
4 Correct 236 ms 23476 KB Output is correct
5 Correct 337 ms 23476 KB Output is correct
6 Correct 193 ms 23476 KB Output is correct
7 Correct 294 ms 23476 KB Output is correct
8 Correct 121 ms 23476 KB Output is correct
9 Correct 73 ms 23476 KB Output is correct