oj.uz

Submission #976948

# Submission time Handle Problem Language Result Execution time Memory
976948 2024-05-07T09:33:17 Z LOLOLO Ball Machine (BOI13_ballmachine) C++17
37.4359 / 100
 159 ms 31260 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) {
    dep[u] = dep[v] + 1;
    mn[u] = u;

    for (auto x : ed[u]) {
        dfs(x, u);
        mn[u] = min(mn[u], mn[x]);
    }

    sort(all(ed[u]), [&] (int a, int b) {return mn[a] < mn[b];});
}

void dfs2(int u, int v) {
    id[u] = timer++;
    for (auto x : ed[u]) {
        dfs2(x, u);
    }
}
 
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);
    dfs2(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
5.76923076923 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 10076 KB Output isn't correct
2 Incorrect 96 ms 19260 KB Output isn't correct
3 Correct 49 ms 19284 KB Output is correct
4 Correct 2 ms 10168 KB Output is correct
5 Incorrect 2 ms 10076 KB Output isn't correct
6 Incorrect 3 ms 10072 KB Output isn't correct
7 Incorrect 3 ms 10072 KB Output isn't correct
8 Incorrect 3 ms 10076 KB Output isn't correct
9 Incorrect 7 ms 10332 KB Output isn't correct
10 Incorrect 20 ms 12888 KB Output isn't correct
11 Incorrect 98 ms 19280 KB Output isn't correct
12 Correct 51 ms 19284 KB Output is correct
13 Incorrect 80 ms 19028 KB Output isn't correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 14564 KB Output is correct
2 Correct 105 ms 26300 KB Output is correct
3 Correct 60 ms 23028 KB Output is correct
4 Correct 55 ms 14712 KB Output is correct
5 Correct 63 ms 14904 KB Output is correct
6 Correct 51 ms 14684 KB Output is correct
7 Correct 51 ms 13912 KB Output is correct
8 Correct 26 ms 14428 KB Output is correct
9 Correct 97 ms 26096 KB Output is correct
10 Correct 108 ms 26200 KB Output is correct
11 Correct 90 ms 26364 KB Output is correct
12 Correct 104 ms 24144 KB Output is correct
13 Correct 65 ms 28584 KB Output is correct
14 Correct 60 ms 22992 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 59 ms 18440 KB Output isn't correct
2 Incorrect 132 ms 24492 KB Output isn't correct
3 Incorrect 74 ms 26332 KB Output isn't correct
4 Incorrect 74 ms 23084 KB Output isn't correct
5 Incorrect 107 ms 22736 KB Output isn't correct
6 Incorrect 78 ms 22676 KB Output isn't correct
7 Incorrect 75 ms 21072 KB Output isn't correct
8 Incorrect 75 ms 26132 KB Output isn't correct
9 Incorrect 159 ms 26784 KB Output isn't correct
10 Incorrect 133 ms 26456 KB Output isn't correct
11 Incorrect 147 ms 26604 KB Output isn't correct
12 Incorrect 149 ms 24528 KB Output isn't correct
13 Incorrect 143 ms 31260 KB Output isn't correct
14 Incorrect 116 ms 22964 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 121 ms 26960 KB Output isn't correct
2 Incorrect 120 ms 24468 KB Output isn't correct
3 Correct 83 ms 29756 KB Output is correct
4 Incorrect 117 ms 26920 KB Output isn't correct
5 Incorrect 116 ms 26412 KB Output isn't correct
6 Incorrect 104 ms 26216 KB Output isn't correct
7 Incorrect 133 ms 24544 KB Output isn't correct
8 Correct 76 ms 29768 KB Output is correct
9 Correct 74 ms 23012 KB Output is correct