Submission #1120007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120007		Captain_Georgia	Ball Machine (BOI13_ballmachine)	C++17	0 / 100	228 ms	34020 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int32_t main () {

    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0); 

    int N, Q;
    cin >> N >> Q;
    vector<int> g[N];
    int root = -1;
    for (int i = 0;i < N;i ++) {
        int p;
        cin >> p;
        -- p;
        if (p != -1) g[p].push_back(i);
        else root = i;
    }
    assert(root != -1);

    const int lg = 20;
    vector<vector<int>> up(lg, vector<int>(N, 0));
    vector<int> tin(N, 0), tout(N, 0), submn(N), depth(N, 0);
    int _time = 0;
    function<void(int, int)> dfs_init = [&](int si, int pi) -> void {
        up[0][si] = pi;
        for (int i = 1;i < lg;i ++) {
            up[i][si] = up[i - 1][up[i - 1][si]];
        }

        submn[si] = si;
        tin[si] = ++ _time;
        for (auto v : g[si]) if (v != pi) {
            depth[v] = depth[si] + 1;
            dfs_init (v, si);
            submn[si] = min(submn[si], submn[v]);
        }
        tout[si] = _time;
    };
    dfs_init (root, root);

    vector<int> all;
    auto cmp = [&](int x, int y) -> bool {
        return submn[x] < submn[y];
    };
    function<void(int, int)> dfs = [&](int si, int pi) -> void {
        sort (g[si].begin(), g[si].end(), cmp);
        // cout << si << " ";
        // for (auto v : g[si]) if (v != pi) {
        //     cout << v << " ";
        // } cout << "\n";
        for (auto v : g[si]) if (v != pi) {
            dfs (v, si);
        }
        all.push_back(si);
    };
    dfs (root, root);
    // for (auto v : all) cout << v << " ";
    // cout << "\n";

    vector<int> val(N + 1);
    set<array<int, 2>> index;
    for (int i = 0;i < all.size();i ++) {
        val[all[i]] = i;
        index.insert({i, all[i]});
    }
    auto is_ancestor = [&](int x, int y) -> bool {
        return (tin[x] <= tin[y] && tout[x] >= tout[y]);
    };
    vector<int> used(N, 0);
    while (Q --) {
        int typ, x;
        cin >> typ >> x;
        if (typ == 1) {
            for (int i = 0;i < x;i ++) {
                assert (index.size() > 0);
                if (i == x - 1) {
                    cout << depth[(*index.begin())[1]] + 1 << "\n";
                }
                used[(*index.begin())[1]] = 1;
                index.erase(index.begin());
            }
        } else {
            -- x;
            int lc = x;
            for (int bt = lg - 1;bt >= 0;bt --) if (used[up[bt][lc]] == 1) {
                lc = up[bt][lc];
            }
            used[lc] = 0;
            index.insert({val[lc], lc});
            cout << depth[x] - depth[lc] << "\n";
        }
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int32_t main()':
ballmachine.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0;i < all.size();i ++) {
      |                    ~~^~~~~~~~~~~~
ballmachine.cpp:71:10: warning: variable 'is_ancestor' set but not used [-Wunused-but-set-variable]
   71 |     auto is_ancestor = [&](int x, int y) -> bool {
      |          ^~~~~~~~~~~

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