Submission #385938

#	Time	Username	Problem	Language	Result	Execution time	Memory
385938		arujbansal	Ball Machine (BOI13_ballmachine)	C++17	17.70 / 100	1093 ms	28264 KiB

ballmachine

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <numeric>
#include <functional>
#include <chrono>
#include <utility>
#include <iomanip>
#include <assert.h>

using namespace std;

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
// #define int long long

const int MXN = 1e5 + 5, INF = 1e9 + 5;
vector<int> adj[MXN];
int par[MXN], tin[MXN], tour[MXN], depth[MXN], valid[MXN], tout[MXN], present[MXN];
int timer, root;
priority_queue<int, vector<int>, greater<>> pq;
set<int> st;

int dfs(int u, int p) {
    int subtree = 1;

    tour[timer] = u;
    tin[u] = timer++;
    depth[u] = depth[p] + 1;

    for (const auto &v : adj[u]) {
        if (v != p) 
            subtree += dfs(v, u);
    }

    if (subtree == 1) {
        pq.push(u);
        valid[u] = 1;

        st.insert(tin[u]);
    }

    tout[u] = timer - 1;

    return subtree;
}

bool is_anc(int u, int v) { return tin[u] <= tin[v] && tout[u] >= tout[v]; }

int add_ball(int k) {
    int last = -1;

    while (k--) {
        assert(!pq.empty());
        int v = pq.top();
        pq.pop();

        if (!valid[v]) continue;
        valid[v] = 0;
        present[v] = 1;

        st.insert(tin[v]);

        for (const auto &node : adj[v]) {
            if (node == par[v]) continue;
            st.erase(tin[node]);
        }

        last = v;

        if (par[v] != 0) {
            bool can_add = true;

            for (const auto &x : adj[par[v]]) {
                if (x == par[par[v]]) continue;
                if (!present[x]) can_add = false;
            }

            if (can_add) {
                pq.emplace(par[v]);
                valid[par[v]] = 1;
            }
        }            
    }

    return last;
}

int remove_ball(int v) {
    auto ancestor = st.upper_bound(tin[v]);
    ancestor--;

    int u = tour[*ancestor];
    valid[u] = true;
    present[u] = false;
    pq.emplace(u);

    st.erase(ancestor);

    for (const auto &x : adj[u]) {
        if (x == par[u]) continue;

        st.insert(tin[x]);
        break;
    }

    return depth[v] - depth[u];
}   

void solve() {
    int N, Q;
    cin >> N >> Q;

    for (int i = 1; i <= N; i++) {
        cin >> par[i];

        if (par[i] == 0) {
            root = i;
            continue;
        }

        adj[i].push_back(par[i]);
        adj[par[i]].push_back(i);
    }

    dfs(root, 0);

    while (Q--) {
        int type, x;
        cin >> type >> x;

        if (type == 1) cout << add_ball(x) << "\n";
        else cout << remove_ball(x) << "\n";
    }
}

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

    int TC = 1;
    // cin >> TC;
    while (TC--) solve();
}

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