oj.uz

Submission #976947

# Submission time Handle Problem Language Result Execution time Memory
976947 2024-05-07T09:31:41 Z LOLOLO Ball Machine (BOI13_ballmachine) C++17
12.381 / 100
 145 ms 31020 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 (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]) {
        dfs(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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 10072 KB Output isn't correct
2 Incorrect 81 ms 19016 KB Output isn't correct
3 Incorrect 61 ms 19284 KB Output isn't correct
4 Incorrect 2 ms 10076 KB Output isn't correct
5 Incorrect 2 ms 10076 KB Output isn't correct
6 Incorrect 3 ms 10076 KB Output isn't correct
7 Incorrect 3 ms 10076 KB Output isn't correct
8 Incorrect 3 ms 10076 KB Output isn't correct
9 Incorrect 7 ms 10332 KB Output isn't correct
10 Incorrect 21 ms 12916 KB Output isn't correct
11 Incorrect 85 ms 19028 KB Output isn't correct
12 Incorrect 55 ms 19100 KB Output isn't correct
13 Incorrect 83 ms 19032 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 14428 KB Output is correct
2 Incorrect 109 ms 26708 KB Output isn't correct
3 Correct 62 ms 22736 KB Output is correct
4 Incorrect 60 ms 14932 KB Output isn't correct
5 Incorrect 55 ms 15196 KB Output isn't correct
6 Incorrect 52 ms 14676 KB Output isn't correct
7 Incorrect 54 ms 14160 KB Output isn't correct
8 Correct 26 ms 14428 KB Output is correct
9 Incorrect 122 ms 27220 KB Output isn't correct
10 Incorrect 108 ms 26708 KB Output isn't correct
11 Incorrect 99 ms 26080 KB Output isn't correct
12 Incorrect 117 ms 24692 KB Output isn't correct
13 Correct 67 ms 28244 KB Output is correct
14 Correct 60 ms 22732 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 18320 KB Output isn't correct
2 Incorrect 145 ms 24404 KB Output isn't correct
3 Incorrect 73 ms 25940 KB Output isn't correct
4 Incorrect 77 ms 22612 KB Output isn't correct
5 Incorrect 81 ms 22364 KB Output isn't correct
6 Incorrect 78 ms 22468 KB Output isn't correct
7 Incorrect 88 ms 21076 KB Output isn't correct
8 Incorrect 86 ms 26036 KB Output isn't correct
9 Incorrect 119 ms 26708 KB Output isn't correct
10 Incorrect 119 ms 26448 KB Output isn't correct
11 Incorrect 119 ms 26452 KB Output isn't correct
12 Incorrect 117 ms 24332 KB Output isn't correct
13 Incorrect 138 ms 31020 KB Output isn't correct
14 Incorrect 113 ms 22732 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 26184 KB Output isn't correct
2 Incorrect 122 ms 24084 KB Output isn't correct
3 Correct 70 ms 29524 KB Output is correct
4 Incorrect 105 ms 26196 KB Output isn't correct
5 Incorrect 101 ms 26228 KB Output isn't correct
6 Incorrect 101 ms 26328 KB Output isn't correct
7 Incorrect 117 ms 24144 KB Output isn't correct
8 Correct 77 ms 29596 KB Output is correct
9 Correct 70 ms 22832 KB Output is correct