oj.uz

Submission #977150

# Submission time Handle Problem Language Result Execution time Memory
977150 2024-05-07T12:28:34 Z LOLOLO Ball Machine (BOI13_ballmachine) C++17
100 / 100
 168 ms 31284 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
#define           f    first
#define           s    second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 2e5 + 100;
vector <int> ed[N];
int sp[N][20], sz[N], is[N], dep[N], mn[N], id[N], timer = 1;

void dfs(int u, int v) {
    dep[u] = dep[v] + 1;
    mn[u] = u;

    for (int i = 1; i < 20; i++) {
        sp[u][i] = sp[sp[u][i - 1]][i - 1];
    }

    for (auto x : ed[u]) {
        dfs(x, u);
        mn[u] = min(mn[u], mn[x]);
    }

    sort(all(ed[u]), [&] (int a, int b) {return mn[a] < mn[b];});
}

void dfs2(int u, int v) {
    id[u] = timer++;
    for (auto x : ed[u]) {
        dfs2(x, u);
    }
}
 
ll solve() {
    mem(mn, 0x3f);
 
    ll n, q, root = 0;
    cin >> n >> q;
 
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        if (x) {
            ed[x].pb(i);
            sz[x]++;
            sp[i][0] = x;
        } else {
            root = i;
        }
    }
 
    dfs(root, root);
    dfs2(root, root);
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < 20; j++) {
            sp[i][j] = sp[sp[i][j - 1]][j - 1];
        }
    }
 
    set <pair <int, int>> st;
    for (int i = 1; i <= n; i++) {
        if (sz[i] == 0) {
            st.insert({id[i], i});
        }
    }
 
    while (q--) {
        int t, x;
        cin >> t >> x;
 
        if (t == 1) {
            int pr = 0;
            for (int i = 1; i <= x; i++) {
                auto t = *st.begin();
                st.erase(t);
                pr = t.s;
                is[pr] = 1;
                sz[sp[pr][0]]--;
 
                if (sp[pr][0] && sz[sp[pr][0]] == 0) {
                    st.insert({id[sp[pr][0]], sp[pr][0]});
                }
            }

            cout << pr << '\n';
        } else {
            int v = x;
            for (int i = 19; i >= 0; i--) {
                if (is[sp[x][i]]) {
                    x = sp[x][i];
                }
            }
 
            sz[sp[x][0]]++;
            is[x] = 0;
 
            if (sp[x][0] && sz[sp[x][0]] == 1) {
                st.erase({id[sp[x][0]], sp[x][0]});
            }
 
            st.insert({id[x], x});
 
            cout << dep[v] - dep[x] << '\n';
        }
    }
 
    return 0;
}
 
int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);
 
    int t = 1;
    //cin >> t;
 
    while (t--) {
        solve();
        //cout << solve() << '\n';
    }
 
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10072 KB Output is correct
2 Correct 99 ms 20308 KB Output is correct
3 Correct 57 ms 20560 KB Output is correct
4 Correct 3 ms 10076 KB Output is correct
5 Correct 3 ms 10076 KB Output is correct
6 Correct 3 ms 10076 KB Output is correct
7 Correct 3 ms 10076 KB Output is correct
8 Correct 3 ms 10076 KB Output is correct
9 Correct 7 ms 10468 KB Output is correct
10 Correct 26 ms 13192 KB Output is correct
11 Correct 125 ms 20340 KB Output is correct
12 Correct 55 ms 20308 KB Output is correct
13 Correct 95 ms 20228 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 14940 KB Output is correct
2 Correct 151 ms 27572 KB Output is correct
3 Correct 70 ms 23824 KB Output is correct
4 Correct 66 ms 16064 KB Output is correct
5 Correct 66 ms 15552 KB Output is correct
6 Correct 57 ms 15440 KB Output is correct
7 Correct 57 ms 14708 KB Output is correct
8 Correct 29 ms 14928 KB Output is correct
9 Correct 131 ms 27624 KB Output is correct
10 Correct 131 ms 27728 KB Output is correct
11 Correct 124 ms 27732 KB Output is correct
12 Correct 154 ms 25476 KB Output is correct
13 Correct 84 ms 29544 KB Output is correct
14 Correct 69 ms 24016 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 18772 KB Output is correct
2 Correct 151 ms 25780 KB Output is correct
3 Correct 101 ms 26264 KB Output is correct
4 Correct 87 ms 23628 KB Output is correct
5 Correct 91 ms 23636 KB Output is correct
6 Correct 91 ms 23620 KB Output is correct
7 Correct 108 ms 21924 KB Output is correct
8 Correct 93 ms 26520 KB Output is correct
9 Correct 126 ms 27704 KB Output is correct
10 Correct 132 ms 27736 KB Output is correct
11 Correct 157 ms 27916 KB Output is correct
12 Correct 140 ms 25684 KB Output is correct
13 Correct 131 ms 31284 KB Output is correct
14 Correct 125 ms 24400 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 27732 KB Output is correct
2 Correct 144 ms 25740 KB Output is correct
3 Correct 101 ms 31060 KB Output is correct
4 Correct 155 ms 28036 KB Output is correct
5 Correct 168 ms 27824 KB Output is correct
6 Correct 150 ms 27788 KB Output is correct
7 Correct 135 ms 25824 KB Output is correct
8 Correct 118 ms 30992 KB Output is correct
9 Correct 76 ms 24012 KB Output is correct