oj.uz

Submission #933898

# Submission time Handle Problem Language Result Execution time Memory
933898 2024-02-26T14:32:12 Z efishel Ball Machine (BOI13_ballmachine) C++17
100 / 100
 120 ms 36808 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 74 ms 24004 KB Output is correct
3 Correct 47 ms 24008 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 2 ms 8792 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 3 ms 8796 KB Output is correct
8 Correct 2 ms 8796 KB Output is correct
9 Correct 6 ms 9320 KB Output is correct
10 Correct 15 ms 12896 KB Output is correct
11 Correct 73 ms 24012 KB Output is correct
12 Correct 55 ms 24008 KB Output is correct
13 Correct 77 ms 24076 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 14796 KB Output is correct
2 Correct 116 ms 32460 KB Output is correct
3 Correct 60 ms 27704 KB Output is correct
4 Correct 43 ms 17724 KB Output is correct
5 Correct 44 ms 17452 KB Output is correct
6 Correct 42 ms 17664 KB Output is correct
7 Correct 46 ms 16860 KB Output is correct
8 Correct 24 ms 14808 KB Output is correct
9 Correct 104 ms 32608 KB Output is correct
10 Correct 110 ms 32380 KB Output is correct
11 Correct 93 ms 32456 KB Output is correct
12 Correct 95 ms 30268 KB Output is correct
13 Correct 69 ms 34296 KB Output is correct
14 Correct 69 ms 27928 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 21788 KB Output is correct
2 Correct 117 ms 30656 KB Output is correct
3 Correct 77 ms 32840 KB Output is correct
4 Correct 88 ms 29824 KB Output is correct
5 Correct 69 ms 29640 KB Output is correct
6 Correct 71 ms 29644 KB Output is correct
7 Correct 68 ms 28108 KB Output is correct
8 Correct 72 ms 32960 KB Output is correct
9 Correct 120 ms 32708 KB Output is correct
10 Correct 118 ms 32624 KB Output is correct
11 Correct 110 ms 32716 KB Output is correct
12 Correct 109 ms 30672 KB Output is correct
13 Correct 117 ms 36808 KB Output is correct
14 Correct 92 ms 27964 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 32868 KB Output is correct
2 Correct 107 ms 30708 KB Output is correct
3 Correct 85 ms 36296 KB Output is correct
4 Correct 113 ms 32848 KB Output is correct
5 Correct 106 ms 32528 KB Output is correct
6 Correct 96 ms 32508 KB Output is correct
7 Correct 101 ms 30664 KB Output is correct
8 Correct 78 ms 36360 KB Output is correct
9 Correct 56 ms 27716 KB Output is correct