oj.uz

Submission #976938

# Submission time Handle Problem Language Result Execution time Memory
976938 2024-05-07T09:25:14 Z LOLOLO Ball Machine (BOI13_ballmachine) C++17
7.53968 / 100
 139 ms 32640 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], id[N], timer = 1;

void dfs(int u, int v) {
    mn[u] = u;
    dep[u] = dep[v] + 1;

    sort(all(ed[u]), [&] (int a, int b) {return mn[a] < mn[b];});
    for (auto x : ed[u]) {
        dfs(x, u);
        mn[u] = min(mn[u], mn[x]);
    }

    id[u] = timer++;
}
 
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 {
            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({id[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 (sp[pr][0] && sz[sp[pr][0]] == 0) {
                    st.insert({id[sp[pr][0]], sp[pr][0]});
                }
            }
 
            cout << pr << '\n';
        } else {
            int v = x;
            for (int i = 19; i >= 0; i--) {
                if (is[sp[x][i]]) {
                    x = sp[x][i];
                }
            }
 
            sz[sp[x][0]]++;
            is[x] = 0;
 
            if (sp[x][0] && sz[sp[x][0]] == 1) {
                st.erase({id[sp[x][0]], sp[x][0]});
            }
 
            st.insert({id[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 10076 KB Output isn't correct
2 Incorrect 91 ms 20388 KB Output isn't correct
3 Incorrect 57 ms 20304 KB Output isn't correct
4 Incorrect 2 ms 10076 KB Output isn't correct
5 Incorrect 2 ms 10164 KB Output isn't correct
6 Incorrect 4 ms 10076 KB Output isn't correct
7 Incorrect 4 ms 10076 KB Output isn't correct
8 Incorrect 4 ms 10212 KB Output isn't correct
9 Incorrect 7 ms 10328 KB Output isn't correct
10 Incorrect 19 ms 13204 KB Output isn't correct
11 Incorrect 129 ms 20392 KB Output isn't correct
12 Incorrect 60 ms 20308 KB Output isn't correct
13 Incorrect 86 ms 20388 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 14924 KB Output is correct
2 Incorrect 103 ms 28256 KB Output isn't correct
3 Incorrect 74 ms 24004 KB Output isn't correct
4 Incorrect 60 ms 15440 KB Output isn't correct
5 Incorrect 56 ms 16052 KB Output isn't correct
6 Incorrect 50 ms 15436 KB Output isn't correct
7 Incorrect 63 ms 14784 KB Output isn't correct
8 Correct 31 ms 14984 KB Output is correct
9 Incorrect 117 ms 28836 KB Output isn't correct
10 Incorrect 115 ms 28120 KB Output isn't correct
11 Incorrect 100 ms 27628 KB Output isn't correct
12 Incorrect 111 ms 25948 KB Output isn't correct
13 Correct 61 ms 29524 KB Output is correct
14 Incorrect 75 ms 24176 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 19280 KB Output isn't correct
2 Incorrect 120 ms 25940 KB Output isn't correct
3 Incorrect 73 ms 27156 KB Output isn't correct
4 Incorrect 71 ms 23712 KB Output isn't correct
5 Incorrect 81 ms 23636 KB Output isn't correct
6 Incorrect 74 ms 23636 KB Output isn't correct
7 Incorrect 73 ms 22100 KB Output isn't correct
8 Incorrect 80 ms 27028 KB Output isn't correct
9 Incorrect 130 ms 28376 KB Output isn't correct
10 Incorrect 112 ms 27752 KB Output isn't correct
11 Incorrect 134 ms 27732 KB Output isn't correct
12 Incorrect 118 ms 25888 KB Output isn't correct
13 Incorrect 139 ms 32640 KB Output isn't correct
14 Incorrect 109 ms 24384 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 104 ms 27500 KB Output isn't correct
2 Incorrect 121 ms 25644 KB Output isn't correct
3 Correct 82 ms 31040 KB Output is correct
4 Incorrect 105 ms 27640 KB Output isn't correct
5 Incorrect 104 ms 27732 KB Output isn't correct
6 Incorrect 92 ms 27540 KB Output isn't correct
7 Incorrect 109 ms 25780 KB Output isn't correct
8 Correct 66 ms 30932 KB Output is correct
9 Incorrect 66 ms 24044 KB Output isn't correct