Submission #933898

#	Time	Username	Problem	Language	Result	Execution time	Memory
933898		efishel	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	120 ms	36808 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector <ll>;

const ll MAXN = 1E5+16, LOG = 18;
vector <pair <ll, ll> > adj[MAXN];
ll anc[MAXN][LOG];
ll dis[MAXN];
ll dp[MAXN];
bool hasBall[MAXN];
vll ord;
ll tout[MAXN];
ll timer=0;

void dfs_prio (ll u, ll par) {
    anc[u][0]=par;
    dp[u]=u+1;
    for (auto &[prio, v] : adj[u]) {
        if (v == par) continue;
        dis[v]=dis[u]+1;
        dfs_prio(v, u);
        prio=dp[v];
        dp[u]=min(dp[u], dp[v]);
    }
    sort(adj[u].begin(), adj[u].end());
}

void dfs_ord (ll u, ll par) {
    for (auto [prio, v] : adj[u]) {
        if (v == par) continue;
        dfs_ord(v, u);
    }
    tout[u] = timer++;
    ord.push_back(u);
}

#define mid ((l+r)>>1)
#define off (2*(mid-l+1))
struct SegTree {
    vll tree;
    ll n;

    SegTree (ll n): tree(2*n, 0), n(n) {}

    void pull (ll l, ll r, ll id) {
        tree[id] = tree[id+1] + tree[id+off];
    }

    void remove (ll at, ll l, ll r, ll id) {
        if (at < l || r < at) return;
        if (at <= l && r <= at) {
            assert(tree[id]);
            tree[id]=0;
            return;
        }
        remove(at, l, mid, id+1);
        remove(at, mid+1, r, id+off);
        pull(l, r, id);
    }

    void remove (ll at) {
        remove(at, 0, n-1, 0);
    }

    ll find_addU (ll l, ll r, ll id) {
        if (l == r) {
            assert(!tree[id]);
            tree[id]=1;
            return ord[l];
        }
        ll u = (tree[id+1] < mid-l+1 ? find_addU(l, mid, id+1) : find_addU(mid+1, r, id+off));
        pull(l, r, id);
        return u;
    }

    ll find_addU () {
        return find_addU(0, n-1, 0);
    }
};

int main () {
    cin.tie(nullptr) -> sync_with_stdio(false);
    ll n, Q;
    cin >> n >> Q;
    ll root;
    for (ll u = 0; u < n; u++) {
        ll v;
        cin >> v;
        v--;
        if (v == -1) root=u;
        else {
            adj[u].push_back({-16, v});
            adj[v].push_back({-16, u});
        }
    }
    dis[root]=0;
    dfs_prio(root, root);
    dfs_ord(root, root);
    for (ll bit = 1; bit < LOG; bit++) {
        for (ll u = 0; u < n; u++) {
            anc[u][bit] = anc[anc[u][bit-1]][bit-1];
        }
    }
    SegTree st(n);
    while (Q--) {
        char type;
        cin >> type;
        switch (type) {
            case '1':
            {ll k;
            cin >> k;
            ll u;
            for (ll i = 0; i < k; i++) {
                u = st.find_addU();
                hasBall[u]=true;
            }
            cout << u+1 << '\n';}
            break;
            case '2':
            {ll u;
            cin >> u;
            u--;
            ll dis1=dis[u];
            for (ll jump=LOG-1; jump >= 0; jump--) {
                if (!hasBall[anc[u][jump]]) continue;
                u = anc[u][jump];
            }
            ll dis2=dis[u];
            hasBall[u]=false;
            st.remove(tout[u]);
            cout << dis1 - dis2 << '\n';}
            break;
        }
    }
    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:118:23: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
  118 |             cout << u+1 << '\n';}
      |                       ^
ballmachine.cpp:99:12: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   99 |     dfs_ord(root, root);
      |     ~~~~~~~^~~~~~~~~~~~

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