Submission #755478

#	Time	Username	Problem	Language	Result	Execution time	Memory
755478		The_Samurai	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	685 ms	29648 KiB

ballmachine

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> g, b_jump;
vector<int> par, way, pos, sub;
vector<bool> ball;

int jump(int u, int h) {
    if (u == -1) return 0;
    if (h == 0) return u;
    int x = 31 - __builtin_clz(h);
    return jump(b_jump[u][x], h - (1 << x));
}

void dfs1(int u) {
    sub[u] = u;
    for (int h = 0; (1 << h) <= way.size(); h++) {
        b_jump[u][h] = way[(int) way.size() - (1 << h)];
    }
    way.emplace_back(u);
    for (int v: g[u]) {
        dfs1(v);
        sub[u] = min(sub[u], sub[v]);
    }
    way.pop_back();
}

void dfs2(int u) {
    for (int v: g[u]) {
        dfs2(v);
    }
    way.emplace_back(u);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    int n, q, h = 0;
    cin >> n >> q;
    while ((1 << h) < n) h++;
    b_jump.assign(n + 1, vector<int>(h + 1, -1));
    g.assign(n + 1, {});
    par.assign(n + 1, 0);
    ball.assign(n + 1, false);
    sub.assign(n + 1, 0);
    pos.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> par[i];
        g[par[i]].emplace_back(i);
    }
    way.clear();
    dfs1(0);
    for (int i = 1; i <= n; i++) {
        sort(g[i].begin(), g[i].end(), [&](int u, int v) {
            return sub[u] < sub[v];
        });
    }
    way.clear();
    dfs2(0);
    set<pair<int, int>> emp;
    for (int i = 0; i < n; i++) {
        emp.insert({i, way[i]});
        pos[way[i]] = i;
    }

    while (q--) {
        int t, x;
        cin >> t >> x;
        if (t == 1) {
            int i = 0, last = 0;
            vector<pair<int, int>> del;
            for (auto it = emp.begin(); i < x; i++, it++) {
                last = (*it).second;
                ball[(*it).second] = true;
                del.push_back(*it);
            }
            for (auto it: del) {
                emp.erase(it);
            }
            cout << last << '\n';
        } else {
            int l = 0, r = n - 1, best = -1;
            while (l <= r) {
                int m = (l + r) >> 1;
                int u = jump(x, m);
                if (ball[u] and !ball[par[u]]) {
                    best = m;
                    break;
                }
                if (ball[par[u]]) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
            assert(best >= 0);
            x = jump(x, best);
            ball[x] = false;
            emp.insert({pos[x], x});
            cout << best << '\n';
        }
    }

    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'void dfs1(int)':
ballmachine.cpp:19:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for (int h = 0; (1 << h) <= way.size(); h++) {
      |                     ~~~~~~~~~^~~~~~~~~~~~~

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