oj.uz

Submission #874783

# Submission time Handle Problem Language Result Execution time Memory
874783 2023-11-17T18:42:16 Z LOLOLO Ball Machine (BOI13_ballmachine) C++14
4.28571 / 100
 165 ms 28500 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];

void dfs(int u, int v) {
    mn[u] = u;
    dep[u] = dep[v] + 1;
    for (auto x : ed[u]) {
        dfs(x, u);
        mn[u] = min(mn[u], mn[x]);
    }
}

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 {
            sp[i][0] = i;
            root = i;
        }
    }

    dfs(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({mn[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;
                
                sz[sp[t.s][0]]--;
                if (sz[sp[t.s][0]] == 0) {
                    st.insert({mn[t.s], sp[t.s][0]});
                }
            }

            cout << pr << '\n';
        } else {
            int cnt = 0, v = x;
            for (int i = 19; i >= 0; i--) {
                if (st.find({mn[sp[x][i]], sp[x][i]}) != st.end()) {
                    x = sp[x][i];
                    cnt += (1 << i);
                }
            }

            sz[sp[x][0]]++;

            if (sz[sp[x][0]] == 1) {
                st.erase({mn[sp[x][0]], sp[x][0]});
            }

            st.insert({mn[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 9564 KB Output isn't correct
2 Incorrect 115 ms 16256 KB Output isn't correct
3 Incorrect 88 ms 16512 KB Output isn't correct
4 Incorrect 2 ms 9564 KB Output isn't correct
5 Incorrect 2 ms 9564 KB Output isn't correct
6 Incorrect 3 ms 9564 KB Output isn't correct
7 Incorrect 3 ms 9564 KB Output isn't correct
8 Incorrect 3 ms 9564 KB Output isn't correct
9 Incorrect 7 ms 9564 KB Output isn't correct
10 Incorrect 20 ms 12124 KB Output isn't correct
11 Incorrect 131 ms 16476 KB Output isn't correct
12 Incorrect 89 ms 16468 KB Output isn't correct
13 Incorrect 146 ms 16252 KB Output isn't correct

Subtask #2
4.28571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 13548 KB Output isn't correct
2 Incorrect 133 ms 24656 KB Output isn't correct
3 Correct 107 ms 22164 KB Output is correct
4 Incorrect 69 ms 13820 KB Output isn't correct
5 Incorrect 74 ms 13788 KB Output isn't correct
6 Incorrect 62 ms 13912 KB Output isn't correct
7 Incorrect 60 ms 13140 KB Output isn't correct
8 Incorrect 22 ms 13588 KB Output isn't correct
9 Incorrect 114 ms 24596 KB Output isn't correct
10 Incorrect 130 ms 24620 KB Output isn't correct
11 Incorrect 130 ms 24628 KB Output isn't correct
12 Incorrect 130 ms 22972 KB Output isn't correct
13 Incorrect 60 ms 24400 KB Output isn't correct
14 Correct 105 ms 22112 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 17372 KB Output isn't correct
2 Incorrect 137 ms 23124 KB Output isn't correct
3 Incorrect 77 ms 23892 KB Output isn't correct
4 Incorrect 158 ms 21684 KB Output isn't correct
5 Incorrect 77 ms 21084 KB Output isn't correct
6 Incorrect 83 ms 21220 KB Output isn't correct
7 Incorrect 92 ms 20052 KB Output isn't correct
8 Incorrect 80 ms 23892 KB Output isn't correct
9 Incorrect 134 ms 25168 KB Output isn't correct
10 Incorrect 127 ms 24668 KB Output isn't correct
11 Incorrect 129 ms 24720 KB Output isn't correct
12 Incorrect 128 ms 23120 KB Output isn't correct
13 Incorrect 136 ms 28500 KB Output isn't correct
14 Incorrect 119 ms 22220 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 122 ms 24656 KB Output isn't correct
2 Incorrect 130 ms 23124 KB Output isn't correct
3 Incorrect 84 ms 27472 KB Output isn't correct
4 Incorrect 126 ms 24484 KB Output isn't correct
5 Incorrect 139 ms 24632 KB Output isn't correct
6 Incorrect 165 ms 24628 KB Output isn't correct
7 Incorrect 137 ms 23132 KB Output isn't correct
8 Incorrect 56 ms 27436 KB Output isn't correct
9 Incorrect 108 ms 22212 KB Output isn't correct