oj.uz

답안 #875015

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
875015 2023-11-18T13:41:17 Z LOLOLO Ball Machine (BOI13_ballmachine) C++14
12.381 / 100
 122 ms 30392 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 {
            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 (sp[pr][0] && sz[sp[pr][0]] == 0) {
                    st.insert({mn[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({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 75 ms 17516 KB Output isn't correct
3 Incorrect 45 ms 17496 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 3 ms 9564 KB Output isn't correct
7 Incorrect 3 ms 9596 KB Output isn't correct
8 Incorrect 3 ms 9564 KB Output isn't correct
9 Incorrect 6 ms 9596 KB Output isn't correct
10 Incorrect 17 ms 12376 KB Output isn't correct
11 Incorrect 76 ms 17492 KB Output isn't correct
12 Incorrect 45 ms 17488 KB Output isn't correct
13 Incorrect 74 ms 17492 KB Output isn't correct

Subtask #2
10.7142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 13916 KB Output is correct
2 Incorrect 102 ms 26704 KB Output isn't correct
3 Correct 54 ms 23244 KB Output is correct
4 Incorrect 50 ms 14476 KB Output isn't correct
5 Incorrect 51 ms 15184 KB Output isn't correct
6 Incorrect 49 ms 14480 KB Output isn't correct
7 Incorrect 48 ms 14076 KB Output isn't correct
8 Correct 25 ms 13916 KB Output is correct
9 Incorrect 92 ms 26844 KB Output isn't correct
10 Incorrect 116 ms 26708 KB Output isn't correct
11 Incorrect 81 ms 26108 KB Output isn't correct
12 Incorrect 96 ms 24660 KB Output isn't correct
13 Correct 60 ms 25428 KB Output is correct
14 Correct 52 ms 23184 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 18004 KB Output isn't correct
2 Incorrect 118 ms 24656 KB Output isn't correct
3 Incorrect 71 ms 25172 KB Output isn't correct
4 Incorrect 73 ms 22300 KB Output isn't correct
5 Incorrect 66 ms 22476 KB Output isn't correct
6 Incorrect 65 ms 22100 KB Output isn't correct
7 Incorrect 74 ms 20952 KB Output isn't correct
8 Incorrect 66 ms 25168 KB Output isn't correct
9 Incorrect 104 ms 26740 KB Output isn't correct
10 Incorrect 122 ms 26380 KB Output isn't correct
11 Incorrect 100 ms 26312 KB Output isn't correct
12 Incorrect 109 ms 24748 KB Output isn't correct
13 Incorrect 103 ms 30392 KB Output isn't correct
14 Incorrect 102 ms 23496 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 89 ms 26116 KB Output isn't correct
2 Incorrect 109 ms 24616 KB Output isn't correct
3 Correct 61 ms 28500 KB Output is correct
4 Incorrect 91 ms 26192 KB Output isn't correct
5 Incorrect 90 ms 25936 KB Output isn't correct
6 Incorrect 92 ms 25952 KB Output isn't correct
7 Incorrect 103 ms 24412 KB Output isn't correct
8 Correct 71 ms 28684 KB Output is correct
9 Correct 60 ms 23176 KB Output is correct