oj.uz

Submission #698167

# Submission time Handle Problem Language Result Execution time Memory
698167 2023-02-12T18:32:33 Z Tigerpants Ball Machine (BOI13_ballmachine) C++17
100 / 100
 255 ms 41816 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 148 ms 21932 KB Output is correct
3 Correct 83 ms 22132 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 7 ms 1652 KB Output is correct
10 Correct 21 ms 5844 KB Output is correct
11 Correct 148 ms 21964 KB Output is correct
12 Correct 83 ms 22092 KB Output is correct
13 Correct 117 ms 21872 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 8268 KB Output is correct
2 Correct 201 ms 37060 KB Output is correct
3 Correct 107 ms 32600 KB Output is correct
4 Correct 72 ms 11668 KB Output is correct
5 Correct 80 ms 11596 KB Output is correct
6 Correct 59 ms 11568 KB Output is correct
7 Correct 64 ms 10144 KB Output is correct
8 Correct 31 ms 8216 KB Output is correct
9 Correct 197 ms 37280 KB Output is correct
10 Correct 209 ms 37004 KB Output is correct
11 Correct 155 ms 37044 KB Output is correct
12 Correct 192 ms 34228 KB Output is correct
13 Correct 132 ms 36808 KB Output is correct
14 Correct 106 ms 32576 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 18916 KB Output is correct
2 Correct 235 ms 35292 KB Output is correct
3 Correct 175 ms 33376 KB Output is correct
4 Correct 153 ms 30012 KB Output is correct
5 Correct 148 ms 29772 KB Output is correct
6 Correct 146 ms 29816 KB Output is correct
7 Correct 146 ms 28184 KB Output is correct
8 Correct 159 ms 33412 KB Output is correct
9 Correct 243 ms 37416 KB Output is correct
10 Correct 244 ms 37232 KB Output is correct
11 Correct 233 ms 37216 KB Output is correct
12 Correct 229 ms 35276 KB Output is correct
13 Correct 255 ms 41816 KB Output is correct
14 Correct 192 ms 32660 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 37560 KB Output is correct
2 Correct 224 ms 35204 KB Output is correct
3 Correct 156 ms 41656 KB Output is correct
4 Correct 253 ms 37540 KB Output is correct
5 Correct 216 ms 37248 KB Output is correct
6 Correct 170 ms 37160 KB Output is correct
7 Correct 238 ms 35584 KB Output is correct
8 Correct 167 ms 41676 KB Output is correct
9 Correct 106 ms 32724 KB Output is correct