Submission #677663

#	Time	Username	Problem	Language	Result	Execution time	Memory
677663		dooompy	Ball Machine (BOI13_ballmachine)	C++17	82.62 / 100	1091 ms	37168 KiB

ballmachine

#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

vector<int> adj[100005];
int jmp[100005][20];
int depth[100005];
vector<int> trav;
bool seen[100005];
map<int, int> fromp, fromv;
int mn[100005];

void dfs(int node, int par = -1) {

    if (!seen[node]) {
        seen[node] = true;
        trav.push_back(node);
    }
    for (int i = 1; i < 20; i++) {
        jmp[node][i] = jmp[jmp[node][i-1]][i-1];
    }

    for (auto nxt : adj[node]) {
        depth[nxt] = depth[node] + 1;
        jmp[nxt][0] = node;
        dfs(nxt, node);
    }
}

void dfs2(int node) {
    mn[node] = node;

    for (auto nxt : adj[node]) {
        dfs2(nxt);

        mn[node] = min(mn[node], mn[nxt]);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("test.txt", "r", stdin);
//    freopen("", "w", stdout);
    int n, q; cin >> n >> q;
    int root = 0;
    for (int i = 1; i <= n; i++) {
        int t; cin >> t;
        if (t == 0) {
            root = i;
            continue;
        }
        adj[t].push_back(i);
    }

    dfs2(root);


    for (int i = 1; i <= n; i++) {
        sort(adj[i].begin(), adj[i].end(), [](int a, int b) {
            return mn[a] > mn[b];
        });
    }


    jmp[root][0] = 1;
    depth[root] = 1;
    dfs(root);

    reverse(trav.begin(), trav.end());

//    for (auto a : trav) cout << a << " ";

    set<int> st;
    for (int i = 1; i <= n; i++) {
        fromp[i] = trav[i - 1];
        fromv[trav[i-1]] = i;
        st.insert(i);
    }

//    for (auto x: trav) cout << x << " ";
//    cout << endl;
//    cout << fromp[184] << " " << fromp[185] << " " << fromp[183] << endl;
//    cout << fromv[212] << endl;

    for (int i = 0; i < q; i++) {
        int a, b; cin >> a >> b;

        if (a == 1) {
            // add

            int lst = -1;
            while (b) {
                auto addedto = *st.begin();
                st.erase(addedto);

                lst = fromp[addedto];
                b--;
            }

            cout << lst << "\n";
        } else {
            // remove node b

            int tempb = b;
            int dist = 0;

            for (int i = 19; i >= 0; i--) {
                int jmpto = jmp[tempb][i];

                if (st.count(fromv[jmpto]) || depth[tempb] - (1 << i) < 1) {
                    continue;
                }


                dist += (1 << i);
                tempb = jmp[tempb][i];
            }

            int idx = fromv[tempb];
            st.insert(idx);
            cout << dist << "\n";
        }
    }
}

• Subtask 1: 25 / 25
• Subtask 2: 25.714285714285715 / 30
• Subtask 3: 28.571428571428573 / 40
• Subtask 4: 3.3333333333333335 / 5