oj.uz

Submission #874763

# Submission time Handle Problem Language Result Execution time Memory
874763 2023-11-17T18:19:11 Z LOLOLO Ball Machine (BOI13_ballmachine) C++14
12.381 / 100
 113 ms 24308 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]);
            }

            st.insert(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 3 ms 10584 KB Output isn't correct
2 Incorrect 76 ms 17568 KB Output isn't correct
3 Incorrect 43 ms 17724 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 10872 KB Output isn't correct
10 Incorrect 16 ms 11352 KB Output isn't correct
11 Incorrect 88 ms 17904 KB Output isn't correct
12 Incorrect 44 ms 17744 KB Output isn't correct
13 Incorrect 65 ms 17496 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 11868 KB Output is correct
2 Incorrect 97 ms 22564 KB Output isn't correct
3 Correct 61 ms 21544 KB Output is correct
4 Incorrect 51 ms 14676 KB Output isn't correct
5 Incorrect 49 ms 14940 KB Output isn't correct
6 Incorrect 43 ms 14424 KB Output isn't correct
7 Incorrect 53 ms 14416 KB Output isn't correct
8 Correct 23 ms 11868 KB Output is correct
9 Incorrect 90 ms 23780 KB Output isn't correct
10 Incorrect 85 ms 22616 KB Output isn't correct
11 Incorrect 75 ms 22044 KB Output isn't correct
12 Incorrect 94 ms 21540 KB Output isn't correct
13 Correct 51 ms 22356 KB Output is correct
14 Correct 54 ms 21456 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 15744 KB Output isn't correct
2 Incorrect 113 ms 21584 KB Output isn't correct
3 Incorrect 61 ms 22400 KB Output isn't correct
4 Incorrect 61 ms 21132 KB Output isn't correct
5 Incorrect 61 ms 21076 KB Output isn't correct
6 Incorrect 72 ms 20996 KB Output isn't correct
7 Incorrect 66 ms 20500 KB Output isn't correct
8 Incorrect 59 ms 22612 KB Output isn't correct
9 Incorrect 113 ms 22728 KB Output isn't correct
10 Incorrect 96 ms 22352 KB Output isn't correct
11 Incorrect 105 ms 22352 KB Output isn't correct
12 Incorrect 103 ms 21584 KB Output isn't correct
13 Incorrect 104 ms 24308 KB Output isn't correct
14 Incorrect 100 ms 21712 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 82 ms 22132 KB Output isn't correct
2 Incorrect 111 ms 21420 KB Output isn't correct
3 Correct 59 ms 23032 KB Output is correct
4 Incorrect 80 ms 22212 KB Output isn't correct
5 Incorrect 93 ms 22028 KB Output isn't correct
6 Incorrect 82 ms 22104 KB Output isn't correct
7 Incorrect 93 ms 21332 KB Output isn't correct
8 Correct 55 ms 23124 KB Output is correct
9 Correct 68 ms 21456 KB Output is correct