oj.uz

Submission #874788

# Submission time Handle Problem Language Result Execution time Memory
874788 2023-11-17T18:51:08 Z LOLOLO Ball Machine (BOI13_ballmachine) C++14
12.381 / 100
 126 ms 28840 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;
                is[pr] = 1;

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

            sz[sp[x][0]]++;
            is[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 9560 KB Output isn't correct
2 Incorrect 86 ms 16416 KB Output isn't correct
3 Incorrect 49 ms 16436 KB Output isn't correct
4 Incorrect 2 ms 9560 KB Output isn't correct
5 Incorrect 2 ms 9560 KB Output isn't correct
6 Incorrect 2 ms 9564 KB Output isn't correct
7 Incorrect 2 ms 9564 KB Output isn't correct
8 Incorrect 3 ms 9564 KB Output isn't correct
9 Incorrect 6 ms 9760 KB Output isn't correct
10 Incorrect 17 ms 12124 KB Output isn't correct
11 Incorrect 84 ms 16220 KB Output isn't correct
12 Incorrect 52 ms 16468 KB Output isn't correct
13 Incorrect 72 ms 16288 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 13404 KB Output is correct
2 Incorrect 103 ms 25244 KB Output isn't correct
3 Correct 53 ms 22220 KB Output is correct
4 Incorrect 56 ms 13904 KB Output isn't correct
5 Incorrect 57 ms 14256 KB Output isn't correct
6 Incorrect 52 ms 13804 KB Output isn't correct
7 Incorrect 50 ms 13148 KB Output isn't correct
8 Correct 24 ms 13400 KB Output is correct
9 Incorrect 88 ms 25428 KB Output isn't correct
10 Incorrect 115 ms 25156 KB Output isn't correct
11 Incorrect 86 ms 24668 KB Output isn't correct
12 Incorrect 91 ms 23124 KB Output isn't correct
13 Correct 61 ms 24392 KB Output is correct
14 Correct 57 ms 22160 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 17488 KB Output isn't correct
2 Incorrect 112 ms 23328 KB Output isn't correct
3 Incorrect 69 ms 24068 KB Output isn't correct
4 Incorrect 69 ms 21584 KB Output isn't correct
5 Incorrect 81 ms 21336 KB Output isn't correct
6 Incorrect 65 ms 21260 KB Output isn't correct
7 Incorrect 63 ms 20004 KB Output isn't correct
8 Incorrect 79 ms 24256 KB Output isn't correct
9 Incorrect 111 ms 25412 KB Output isn't correct
10 Incorrect 126 ms 25140 KB Output isn't correct
11 Incorrect 124 ms 24912 KB Output isn't correct
12 Incorrect 101 ms 23332 KB Output isn't correct
13 Incorrect 106 ms 28840 KB Output isn't correct
14 Incorrect 101 ms 22224 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 91 ms 24656 KB Output isn't correct
2 Incorrect 112 ms 23120 KB Output isn't correct
3 Correct 68 ms 27564 KB Output is correct
4 Incorrect 88 ms 24656 KB Output isn't correct
5 Incorrect 105 ms 24656 KB Output isn't correct
6 Incorrect 82 ms 24668 KB Output isn't correct
7 Incorrect 108 ms 23152 KB Output isn't correct
8 Correct 61 ms 27472 KB Output is correct
9 Correct 58 ms 22184 KB Output is correct