Submission #527927

#	Time	Username	Problem	Language	Result	Execution time	Memory
527927		jalsol	Ball Machine (BOI13_ballmachine)	C++11	100 / 100	144 ms	23100 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;

#define Task ""

struct __Init__ {
    __Init__() {
        cin.tie(nullptr)->sync_with_stdio(false);
        if (fopen(Task".inp", "r")) {
            freopen(Task".inp", "r", stdin);
            freopen(Task".out", "w", stdout); }
    }
} __init__;

using ll = long long;

#ifdef LOCAL
#define debug(x) cerr << "[" #x " = " << x << "]\n";
#else
#define debug(...)
#endif // LOCAL

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)

template<class C> int isz(const C& c) { return c.size(); }
template<class T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }

constexpr int eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;

// =============================================================================

constexpr int maxN = 1e5 + 5;
constexpr int logN = 18;

int n, nq;
vector<int> g[maxN];
int root;

int par[maxN][logN];
int minChild[maxN];
int dep[maxN];

int label[maxN];
int rLabel[maxN];
int timer;
priority_queue<int, vector<int>, greater<int>> pq;
bool hasBall[maxN];

void Dfs(int u) {
    minChild[u] = u;

    for (int v : g[u]) {
        dep[v] = dep[u] + 1;
        Dfs(v);
        chmin(minChild[u], minChild[v]);
    }
}

void relabel(int u) {
    sort(all(g[u]), [&](int u, int v) {
        return minChild[u] < minChild[v];
    });

    for (int v : g[u]) {
        relabel(v);
    }

    label[u] = ++timer;
    rLabel[timer] = u;
    pq.push(timer);
}

signed main() {
    cin >> n >> nq;

    For (i, 1, n) {
        int x; cin >> x;

        if (x == 0) {
            root = i;
        } else {
            par[i][0] = x;
            g[x].push_back(i);
        }
    }

    For (j, 1, logN - 1) {
        For (i, 1, n) {
            par[i][j] = par[par[i][j - 1]][j - 1];
        }
    }

    Dfs(root);
    relabel(root);

    Rep (_, nq) {
        int op, val; cin >> op >> val;

        if (op == 1) {
            /// how tf is this possible???
            int u = -1;

            Rep (__, val) {
                u = rLabel[pq.top()]; pq.pop();
                hasBall[u] = true;
            }

            cout << u << '\n';
        } else {
            int u = val;

            Repd (i, logN) {
                if (hasBall[par[u][i]]) {
                    u = par[u][i];
                }
            }

            hasBall[u] = false;
            pq.push(label[u]);
            cout << dep[val] - dep[u] << '\n';
        }
    }
}

/**

**/

Compilation message (stderr)

ballmachine.cpp: In constructor '__Init__::__Init__()':
ballmachine.cpp:11:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |             freopen(Task".inp", "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:12:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |             freopen(Task".out", "w", stdout); }
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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