oj.uz

답안 #874787

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
874787 2023-11-17T18:50:12 Z LOLOLO Ball Machine (BOI13_ballmachine) C++14
12.381 / 100
 111 ms 28244 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[sp[x][0]] = 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 9560 KB Output isn't correct
2 Incorrect 69 ms 16220 KB Output isn't correct
3 Incorrect 56 ms 16504 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 9560 KB Output isn't correct
9 Incorrect 7 ms 9756 KB Output isn't correct
10 Incorrect 15 ms 12308 KB Output isn't correct
11 Incorrect 72 ms 16260 KB Output isn't correct
12 Incorrect 52 ms 16464 KB Output isn't correct
13 Incorrect 67 ms 16280 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 13604 KB Output is correct
2 Incorrect 106 ms 24656 KB Output isn't correct
3 Correct 54 ms 22248 KB Output is correct
4 Incorrect 53 ms 14160 KB Output isn't correct
5 Incorrect 47 ms 14176 KB Output isn't correct
6 Incorrect 41 ms 13660 KB Output isn't correct
7 Incorrect 43 ms 13148 KB Output isn't correct
8 Correct 25 ms 13404 KB Output is correct
9 Incorrect 89 ms 25292 KB Output isn't correct
10 Incorrect 92 ms 24636 KB Output isn't correct
11 Incorrect 76 ms 24708 KB Output isn't correct
12 Incorrect 105 ms 23120 KB Output isn't correct
13 Correct 59 ms 24400 KB Output is correct
14 Correct 51 ms 22060 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 17064 KB Output isn't correct
2 Incorrect 103 ms 23092 KB Output isn't correct
3 Incorrect 73 ms 23892 KB Output isn't correct
4 Incorrect 61 ms 21164 KB Output isn't correct
5 Incorrect 59 ms 21328 KB Output isn't correct
6 Incorrect 64 ms 21292 KB Output isn't correct
7 Incorrect 64 ms 20044 KB Output isn't correct
8 Incorrect 64 ms 23892 KB Output isn't correct
9 Incorrect 91 ms 24660 KB Output isn't correct
10 Incorrect 101 ms 25184 KB Output isn't correct
11 Incorrect 95 ms 24660 KB Output isn't correct
12 Incorrect 91 ms 23120 KB Output isn't correct
13 Incorrect 105 ms 28244 KB Output isn't correct
14 Incorrect 89 ms 22224 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 99 ms 24664 KB Output isn't correct
2 Incorrect 87 ms 23232 KB Output isn't correct
3 Correct 61 ms 27532 KB Output is correct
4 Incorrect 84 ms 24608 KB Output isn't correct
5 Incorrect 111 ms 24912 KB Output isn't correct
6 Incorrect 79 ms 24828 KB Output isn't correct
7 Incorrect 87 ms 23104 KB Output isn't correct
8 Correct 63 ms 27432 KB Output is correct
9 Correct 61 ms 22100 KB Output is correct