oj.uz

Submission #874785

# Submission time Handle Problem Language Result Execution time Memory
874785 2023-11-17T18:43:35 Z LOLOLO Ball Machine (BOI13_ballmachine) C++14
4.28571 / 100
 150 ms 28464 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[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 (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 3 ms 9560 KB Output isn't correct
2 Incorrect 117 ms 16332 KB Output isn't correct
3 Incorrect 89 ms 16600 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 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 7 ms 9564 KB Output isn't correct
10 Incorrect 22 ms 12320 KB Output isn't correct
11 Incorrect 136 ms 16220 KB Output isn't correct
12 Incorrect 88 ms 16536 KB Output isn't correct
13 Incorrect 144 ms 16220 KB Output isn't correct

Subtask #2
4.28571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 13400 KB Output isn't correct
2 Incorrect 150 ms 24656 KB Output isn't correct
3 Correct 107 ms 22172 KB Output is correct
4 Incorrect 67 ms 13656 KB Output isn't correct
5 Incorrect 66 ms 13660 KB Output isn't correct
6 Incorrect 59 ms 13656 KB Output isn't correct
7 Incorrect 60 ms 13124 KB Output isn't correct
8 Incorrect 31 ms 13656 KB Output isn't correct
9 Incorrect 107 ms 24404 KB Output isn't correct
10 Incorrect 129 ms 24660 KB Output isn't correct
11 Incorrect 129 ms 24624 KB Output isn't correct
12 Incorrect 122 ms 22944 KB Output isn't correct
13 Incorrect 60 ms 24268 KB Output isn't correct
14 Correct 104 ms 22164 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 65 ms 17236 KB Output isn't correct
2 Incorrect 134 ms 23100 KB Output isn't correct
3 Incorrect 80 ms 23892 KB Output isn't correct
4 Incorrect 137 ms 21332 KB Output isn't correct
5 Incorrect 78 ms 21344 KB Output isn't correct
6 Incorrect 78 ms 21204 KB Output isn't correct
7 Incorrect 93 ms 20312 KB Output isn't correct
8 Incorrect 85 ms 24032 KB Output isn't correct
9 Incorrect 129 ms 25172 KB Output isn't correct
10 Incorrect 130 ms 24636 KB Output isn't correct
11 Incorrect 137 ms 24772 KB Output isn't correct
12 Incorrect 128 ms 23124 KB Output isn't correct
13 Incorrect 131 ms 28464 KB Output isn't correct
14 Incorrect 126 ms 22732 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 24564 KB Output isn't correct
2 Incorrect 120 ms 23184 KB Output isn't correct
3 Incorrect 60 ms 27472 KB Output isn't correct
4 Incorrect 129 ms 24712 KB Output isn't correct
5 Incorrect 139 ms 24656 KB Output isn't correct
6 Incorrect 145 ms 24640 KB Output isn't correct
7 Incorrect 126 ms 23120 KB Output isn't correct
8 Incorrect 57 ms 27520 KB Output isn't correct
9 Incorrect 105 ms 22220 KB Output isn't correct