oj.uz

답안 #874781

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
874781 2023-11-17T18:38:00 Z LOLOLO Ball Machine (BOI13_ballmachine) C++14
4.28571 / 100
 150 ms 24148 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];

void dfs(int u, int v) {
    dep[u] = dep[v] + 1;
    for (auto x : ed[u]) {
        dfs(x, u);
    }
}

ll solve() {
    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 <int> st;
    for (int i = 1; i <= n; i++) {
        if (sz[i] == 0) {
            st.insert(i);
        }
    }

    while (q--) {
        int t, x;
        cin >> t >> x;

        if (t == 1) {
            int pr = 0;
            for (int i = 1; i <= x; i++) {
                int t = *st.begin();
                st.erase(t);
                pr = t;
                
                sz[sp[t][0]]--;
                if (sz[sp[t][0]] == 0) {
                    st.insert(sp[t][0]);
                }
            }

            cout << pr << '\n';
        } else {
            int cnt = 0, v = x;
            for (int i = 19; i >= 0; i--) {
                if (st.find(sp[x][i]) != st.end()) {
                    x = sp[x][i];
                    cnt += (1 << i);
                }
            }

            sz[sp[x][0]]++;

            if (sz[sp[x][0]] == 1) {
                st.erase(sp[x][0]);
            }

            st.insert(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 10588 KB Output isn't correct
2 Incorrect 108 ms 17564 KB Output isn't correct
3 Incorrect 51 ms 17748 KB Output isn't correct
4 Incorrect 2 ms 10588 KB Output isn't correct
5 Incorrect 3 ms 10588 KB Output isn't correct
6 Incorrect 3 ms 10588 KB Output isn't correct
7 Incorrect 3 ms 10588 KB Output isn't correct
8 Incorrect 3 ms 10588 KB Output isn't correct
9 Incorrect 8 ms 10868 KB Output isn't correct
10 Incorrect 20 ms 11396 KB Output isn't correct
11 Incorrect 112 ms 17500 KB Output isn't correct
12 Incorrect 53 ms 17764 KB Output isn't correct
13 Incorrect 93 ms 17500 KB Output isn't correct

Subtask #2
4.28571428571 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 11864 KB Output isn't correct
2 Incorrect 113 ms 22080 KB Output isn't correct
3 Correct 65 ms 21320 KB Output is correct
4 Incorrect 61 ms 14420 KB Output isn't correct
5 Incorrect 64 ms 14448 KB Output isn't correct
6 Incorrect 52 ms 14668 KB Output isn't correct
7 Incorrect 72 ms 14128 KB Output isn't correct
8 Incorrect 21 ms 11876 KB Output isn't correct
9 Incorrect 117 ms 21840 KB Output isn't correct
10 Incorrect 112 ms 22100 KB Output isn't correct
11 Incorrect 91 ms 22096 KB Output isn't correct
12 Incorrect 116 ms 21296 KB Output isn't correct
13 Incorrect 47 ms 22356 KB Output isn't correct
14 Correct 65 ms 21388 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 58 ms 15440 KB Output isn't correct
2 Incorrect 129 ms 21400 KB Output isn't correct
3 Incorrect 74 ms 22324 KB Output isn't correct
4 Incorrect 76 ms 20828 KB Output isn't correct
5 Incorrect 81 ms 21020 KB Output isn't correct
6 Incorrect 81 ms 21076 KB Output isn't correct
7 Incorrect 82 ms 20564 KB Output isn't correct
8 Incorrect 72 ms 22352 KB Output isn't correct
9 Incorrect 124 ms 22356 KB Output isn't correct
10 Incorrect 150 ms 22036 KB Output isn't correct
11 Incorrect 127 ms 22100 KB Output isn't correct
12 Incorrect 128 ms 21340 KB Output isn't correct
13 Incorrect 118 ms 24148 KB Output isn't correct
14 Incorrect 120 ms 21448 KB Output isn't correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 112 ms 21856 KB Output isn't correct
2 Incorrect 127 ms 21328 KB Output isn't correct
3 Incorrect 56 ms 23124 KB Output isn't correct
4 Incorrect 118 ms 22352 KB Output isn't correct
5 Incorrect 116 ms 22032 KB Output isn't correct
6 Incorrect 98 ms 22044 KB Output isn't correct
7 Incorrect 119 ms 21340 KB Output isn't correct
8 Incorrect 53 ms 23120 KB Output isn't correct
9 Incorrect 63 ms 21456 KB Output isn't correct