oj.uz

Submission #976945

# Submission time Handle Problem Language Result Execution time Memory
976945 2024-05-07T09:30:46 Z LOLOLO Ball Machine (BOI13_ballmachine) C++17
12.381 / 100
 150 ms 30920 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) {
    for (auto x : ed[u]) {
        dfs(x, u);
    }

    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);
    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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 10072 KB Output isn't correct
2 Incorrect 86 ms 18964 KB Output isn't correct
3 Incorrect 58 ms 19096 KB Output isn't correct
4 Incorrect 2 ms 10076 KB Output isn't correct
5 Incorrect 2 ms 10072 KB Output isn't correct
6 Incorrect 3 ms 10328 KB Output isn't correct
7 Incorrect 3 ms 10076 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 18 ms 12896 KB Output isn't correct
11 Incorrect 89 ms 19024 KB Output isn't correct
12 Incorrect 51 ms 19180 KB Output isn't correct
13 Incorrect 79 ms 19028 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 14680 KB Output is correct
2 Incorrect 123 ms 26744 KB Output isn't correct
3 Correct 62 ms 22696 KB Output is correct
4 Incorrect 58 ms 14928 KB Output isn't correct
5 Incorrect 55 ms 15188 KB Output isn't correct
6 Incorrect 50 ms 14428 KB Output isn't correct
7 Incorrect 52 ms 14168 KB Output isn't correct
8 Correct 26 ms 14296 KB Output is correct
9 Incorrect 110 ms 27228 KB Output isn't correct
10 Incorrect 107 ms 26768 KB Output isn't correct
11 Incorrect 109 ms 26472 KB Output isn't correct
12 Incorrect 101 ms 24236 KB Output isn't correct
13 Correct 63 ms 28332 KB Output is correct
14 Correct 60 ms 22804 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 18512 KB Output isn't correct
2 Incorrect 117 ms 24400 KB Output isn't correct
3 Incorrect 76 ms 26044 KB Output isn't correct
4 Incorrect 73 ms 22608 KB Output isn't correct
5 Incorrect 71 ms 22508 KB Output isn't correct
6 Incorrect 72 ms 22364 KB Output isn't correct
7 Incorrect 78 ms 21076 KB Output isn't correct
8 Incorrect 99 ms 25940 KB Output isn't correct
9 Incorrect 120 ms 26708 KB Output isn't correct
10 Incorrect 121 ms 26304 KB Output isn't correct
11 Incorrect 123 ms 26564 KB Output isn't correct
12 Incorrect 150 ms 24404 KB Output isn't correct
13 Incorrect 140 ms 30920 KB Output isn't correct
14 Incorrect 114 ms 22744 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 106 ms 26192 KB Output isn't correct
2 Incorrect 117 ms 24144 KB Output isn't correct
3 Correct 68 ms 29524 KB Output is correct
4 Incorrect 106 ms 26220 KB Output isn't correct
5 Incorrect 122 ms 26192 KB Output isn't correct
6 Incorrect 94 ms 26192 KB Output isn't correct
7 Incorrect 113 ms 24224 KB Output isn't correct
8 Correct 71 ms 29616 KB Output is correct
9 Correct 69 ms 22744 KB Output is correct