Submission #698167

#	Time	Username	Problem	Language	Result	Execution time	Memory
698167		Tigerpants	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	255 ms	41816 KiB

ballmachine

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef set<pll> spll;
typedef vector<bool> vb;
typedef vector<vpll> vvpll;

#define rep(i, a, b) for (ll i = a; i < b; i++)
#define mp(a, b) make_pair(a, b)
#define resz(a, b) a.resize(b)
#define sz(a) a.size()
#define fillsz(a, b) fill_n(a.begin(), sz(a), b)

const ll LOGN = 20;

ll N, Q;

vll order;
spll slots;
vvll up;
vvpll children;
vll depth;

vb has_ball;

ll root;

ll root_tree(ll cur) {
    ll min_subtree_cur = cur;
    rep(i, 0, sz(children[cur])) {
        depth[children[cur][i].second] = depth[cur] + 1;
        children[cur][i] = mp(root_tree(children[cur][i].second), children[cur][i].second);
        min_subtree_cur = min<ll>(min_subtree_cur, children[cur][i].first);
    }
    sort(children[cur].begin(), children[cur].end());
    return min_subtree_cur;
}

ll cnt = 0;
void order_tree(ll cur) {
    for (vpll::iterator child = children[cur].begin(); child != children[cur].end(); child++) {
        order_tree(child->second);
    }
    order[cur] = cnt;
    cnt++;
}

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

    cin >> N >> Q;

    resz(order, N);
    resz(up, N);
    resz(children, N);
    resz(depth, N);
    rep(i, 0, N) {resz(up[i], LOGN); fillsz(up[i], -1);}

    resz(has_ball, N);
    fillsz(has_ball, false);

    rep(i, 0, N) {
        cin >> up[i][0];
        if (up[i][0] == 0) root = i;
        else {up[i][0]--; children[up[i][0]].push_back(mp(0, i));}
    }

    depth[root] = 0;
    root_tree(root);
    order_tree(root);

    up[root][0] = root;
    
    rep(i, 0, LOGN - 1) {
        rep(j, 0, N) {
            up[j][i + 1] = up[up[j][i]][i];
        }
    }

    rep(i, 0, N) {
        slots.insert(mp(order[i], i));
    }

    rep(q, 0, Q) {
        ll type, num;
        cin >> type >> num;
        if (type == 1) {
            rep(i, 0, num) {
                if (i == num - 1) {
                    cout << slots.begin()->second + 1 << "\n";
                }
                has_ball[slots.begin()->second] = true;
                slots.erase(slots.begin());
            }
        } else {
            num--;
            ll under = depth[num];
            for (ll i = LOGN - 1; i >= 0; i--) {
                if (has_ball[up[num][i]]) num = up[num][i];
            }
            has_ball[num] = false;
            slots.insert(mp(order[num], num));
            cout << under - depth[num] << "\n";
        }
    }

    cout << flush;

    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'll root_tree(ll)':
ballmachine.cpp:18:39: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 | #define rep(i, a, b) for (ll i = a; i < b; i++)
      |                                       ^
ballmachine.cpp:40:5: note: in expansion of macro 'rep'
   40 |     rep(i, 0, sz(children[cur])) {
      |     ^~~

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