oj.uz

Submission #410816

# Submission time Handle Problem Language Result Execution time Memory
410816 2021-05-23T19:03:55 Z Victor Ball Machine (BOI13_ballmachine) C++17
100 / 100
 663 ms 23312 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 467 ms 14168 KB Output is correct
3 Correct 314 ms 14404 KB Output is correct
4 Correct 5 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 7 ms 9676 KB Output is correct
7 Correct 8 ms 9676 KB Output is correct
8 Correct 11 ms 9676 KB Output is correct
9 Correct 30 ms 9984 KB Output is correct
10 Correct 88 ms 10812 KB Output is correct
11 Correct 442 ms 14148 KB Output is correct
12 Correct 317 ms 14400 KB Output is correct
13 Correct 454 ms 14180 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 12544 KB Output is correct
2 Correct 605 ms 19628 KB Output is correct
3 Correct 378 ms 16444 KB Output is correct
4 Correct 303 ms 12804 KB Output is correct
5 Correct 392 ms 12612 KB Output is correct
6 Correct 370 ms 12700 KB Output is correct
7 Correct 346 ms 12268 KB Output is correct
8 Correct 202 ms 12540 KB Output is correct
9 Correct 534 ms 20064 KB Output is correct
10 Correct 602 ms 19600 KB Output is correct
11 Correct 531 ms 19368 KB Output is correct
12 Correct 584 ms 18176 KB Output is correct
13 Correct 306 ms 21704 KB Output is correct
14 Correct 351 ms 16576 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 14784 KB Output is correct
2 Correct 622 ms 18620 KB Output is correct
3 Correct 344 ms 20292 KB Output is correct
4 Correct 326 ms 17824 KB Output is correct
5 Correct 370 ms 17512 KB Output is correct
6 Correct 375 ms 17412 KB Output is correct
7 Correct 367 ms 16668 KB Output is correct
8 Correct 351 ms 20304 KB Output is correct
9 Correct 524 ms 20136 KB Output is correct
10 Correct 600 ms 19540 KB Output is correct
11 Correct 597 ms 19688 KB Output is correct
12 Correct 607 ms 18660 KB Output is correct
13 Correct 572 ms 23312 KB Output is correct
14 Correct 441 ms 16580 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 564 ms 20152 KB Output is correct
2 Correct 605 ms 18668 KB Output is correct
3 Correct 320 ms 23260 KB Output is correct
4 Correct 547 ms 20036 KB Output is correct
5 Correct 663 ms 19600 KB Output is correct
6 Correct 556 ms 19636 KB Output is correct
7 Correct 623 ms 18584 KB Output is correct
8 Correct 320 ms 23260 KB Output is correct
9 Correct 349 ms 16756 KB Output is correct