oj.uz

답안 #874782

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
874782 2023-11-17T18:41:41 Z LOLOLO Ball Machine (BOI13_ballmachine) C++14
9.12698 / 100
 186 ms 27088 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]) {
        mn[u] = min(mn[u], mn[x]);
        dfs(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 {
            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;
                
                sz[sp[t.s][0]]--;
                if (sz[sp[t.s][0]] == 0) {
                    st.insert({mn[t.s], sp[t.s][0]});
                }
            }

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

            sz[sp[x][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 9564 KB Output isn't correct
2 Incorrect 125 ms 16332 KB Output isn't correct
3 Incorrect 88 ms 16620 KB Output isn't correct
4 Incorrect 2 ms 9560 KB Output isn't correct
5 Incorrect 2 ms 9392 KB Output isn't correct
6 Incorrect 2 ms 9564 KB Output isn't correct
7 Incorrect 3 ms 9564 KB Output isn't correct
8 Incorrect 3 ms 9564 KB Output isn't correct
9 Incorrect 7 ms 9748 KB Output isn't correct
10 Incorrect 21 ms 12120 KB Output isn't correct
11 Incorrect 158 ms 16468 KB Output isn't correct
12 Incorrect 90 ms 16624 KB Output isn't correct
13 Incorrect 126 ms 16396 KB Output isn't correct

Subtask #2
8.57142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 13180 KB Output is correct
2 Incorrect 141 ms 23868 KB Output isn't correct
3 Correct 106 ms 22224 KB Output is correct
4 Incorrect 61 ms 13520 KB Output isn't correct
5 Incorrect 72 ms 13912 KB Output isn't correct
6 Incorrect 58 ms 13524 KB Output isn't correct
7 Incorrect 57 ms 13064 KB Output isn't correct
8 Correct 22 ms 13148 KB Output is correct
9 Incorrect 159 ms 23700 KB Output isn't correct
10 Incorrect 148 ms 23860 KB Output isn't correct
11 Incorrect 129 ms 23892 KB Output isn't correct
12 Incorrect 121 ms 22744 KB Output isn't correct
13 Incorrect 48 ms 22864 KB Output isn't correct
14 Correct 105 ms 22220 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 67 ms 16780 KB Output isn't correct
2 Incorrect 146 ms 22840 KB Output isn't correct
3 Incorrect 81 ms 22864 KB Output isn't correct
4 Incorrect 83 ms 20444 KB Output isn't correct
5 Incorrect 95 ms 20820 KB Output isn't correct
6 Incorrect 86 ms 20560 KB Output isn't correct
7 Incorrect 78 ms 19724 KB Output isn't correct
8 Incorrect 77 ms 22836 KB Output isn't correct
9 Incorrect 133 ms 24400 KB Output isn't correct
10 Incorrect 159 ms 23876 KB Output isn't correct
11 Incorrect 131 ms 23888 KB Output isn't correct
12 Incorrect 136 ms 22864 KB Output isn't correct
13 Incorrect 158 ms 27088 KB Output isn't correct
14 Incorrect 114 ms 22220 KB Output isn't correct

Subtask #4
0.555555555556 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 131 ms 23636 KB Output isn't correct
2 Incorrect 123 ms 22732 KB Output isn't correct
3 Incorrect 65 ms 25856 KB Output isn't correct
4 Incorrect 135 ms 23784 KB Output isn't correct
5 Incorrect 186 ms 23948 KB Output isn't correct
6 Incorrect 155 ms 23892 KB Output isn't correct
7 Incorrect 121 ms 22696 KB Output isn't correct
8 Incorrect 57 ms 25936 KB Output isn't correct
9 Correct 107 ms 22220 KB Output is correct