oj.uz

Submission #874741

# Submission time Handle Problem Language Result Execution time Memory
874741 2023-11-17T17:55:07 Z LOLOLO Ball Machine (BOI13_ballmachine) C++14
0 / 100
 111 ms 24412 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];

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

ll solve() {
    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 <int> st;
    for (int i = 1; i <= n; i++) {
        if (sz[i] == 0) {
            st.insert(i);
        }
    }

    while (q--) {
        int t, x;
        cin >> t >> x;

        if (t == 1) {
            int pr = 0;
            for (int i = 1; i <= x; i++) {
                int t = *st.begin();
                st.erase(t);
                pr = t;
                is[t] = 1;
                sz[sp[t][0]]--;
                if (sz[sp[t][0]] == 0) {
                    st.insert(sp[t][0]);
                }
            }

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

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

            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 10588 KB Output isn't correct
2 Incorrect 56 ms 18848 KB Output isn't correct
3 Incorrect 45 ms 18772 KB Output isn't correct
4 Incorrect 2 ms 10584 KB Output isn't correct
5 Incorrect 3 ms 10588 KB Output isn't correct
6 Incorrect 3 ms 10588 KB Output isn't correct
7 Incorrect 3 ms 10588 KB Output isn't correct
8 Incorrect 3 ms 10588 KB Output isn't correct
9 Incorrect 6 ms 10844 KB Output isn't correct
10 Incorrect 14 ms 11608 KB Output isn't correct
11 Incorrect 55 ms 18772 KB Output isn't correct
12 Incorrect 47 ms 18768 KB Output isn't correct
13 Incorrect 60 ms 18772 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 12632 KB Output isn't correct
2 Incorrect 64 ms 23380 KB Output isn't correct
3 Incorrect 61 ms 22440 KB Output isn't correct
4 Incorrect 32 ms 15188 KB Output isn't correct
5 Incorrect 32 ms 15196 KB Output isn't correct
6 Incorrect 32 ms 15196 KB Output isn't correct
7 Incorrect 37 ms 14972 KB Output isn't correct
8 Incorrect 21 ms 12636 KB Output isn't correct
9 Incorrect 64 ms 23312 KB Output isn't correct
10 Incorrect 65 ms 23380 KB Output isn't correct
11 Incorrect 67 ms 23412 KB Output isn't correct
12 Incorrect 68 ms 23120 KB Output isn't correct
13 Incorrect 55 ms 23496 KB Output isn't correct
14 Incorrect 59 ms 22480 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 16248 KB Output isn't correct
2 Incorrect 111 ms 22768 KB Output isn't correct
3 Incorrect 47 ms 22612 KB Output isn't correct
4 Incorrect 54 ms 21724 KB Output isn't correct
5 Incorrect 48 ms 21852 KB Output isn't correct
6 Incorrect 55 ms 22352 KB Output isn't correct
7 Incorrect 47 ms 21328 KB Output isn't correct
8 Incorrect 47 ms 22484 KB Output isn't correct
9 Incorrect 72 ms 23276 KB Output isn't correct
10 Incorrect 89 ms 23564 KB Output isn't correct
11 Incorrect 91 ms 23572 KB Output isn't correct
12 Incorrect 76 ms 22868 KB Output isn't correct
13 Incorrect 68 ms 24256 KB Output isn't correct
14 Incorrect 81 ms 22816 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 23740 KB Output isn't correct
2 Incorrect 70 ms 22860 KB Output isn't correct
3 Incorrect 51 ms 24412 KB Output isn't correct
4 Incorrect 72 ms 23364 KB Output isn't correct
5 Incorrect 65 ms 23380 KB Output isn't correct
6 Incorrect 73 ms 23960 KB Output isn't correct
7 Incorrect 70 ms 22896 KB Output isn't correct
8 Incorrect 73 ms 24144 KB Output isn't correct
9 Incorrect 56 ms 22480 KB Output isn't correct