Submission #1292324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292324		kam	Ball Machine (BOI13_ballmachine)	C++20	100 / 100	267 ms	28948 KiB

ballmachine

#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<cassert>
#include<numeric>
#include<vector>
#include<string>
#include<chrono>
#include<random>
#include<stack>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<ios>
using namespace std;
int n, q, root, qq = 0, sz = 21;
vector<vector<int>>gp, up;
vector<int>sub, qth, rqth, black;

bool cm(int& a, int& b) {
    return sub[a] < sub[b];
}

void dfss(int u, int p) {
    for (int& v : gp[u]) {
        if (v == p)continue;
        dfss(v, u);
        sub[u] = min(sub[v], sub[u]);
    }
}

void build(int u, int p) {
    up[u][0] = p;
    for (int i = 1; i < sz; i++) {
        if (up[u][i - 1] == -1)break;
        up[u][i] = up[up[u][i - 1]][i - 1];
    }
    for (int& v : gp[u]) {
        if (v == p)continue;
        build(v, u);
    }
}

vector<int> get(int u) {
    int res = 0;
    for (int i = sz - 1; i >= 0; i--) {
        if (up[u][i] == -1)continue;
        if (black[up[u][i]])u = up[u][i], res += (1 << i);
    }
    return { u,res };
}

void order(int u, int p) {
    for (int& v : gp[u]) {
        if (v == p)continue;
        order(v, u);
    }
    rqth[u] = qq;
    qth[qq++] = u;
}

signed main() {
    cin >> n >> q;
    sub = qth = rqth = black = vector<int>(n);
    gp = vector<vector<int>>(n);
    up = vector<vector<int>>(n, vector<int>(sz, -1));
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        if (x == 0) {
            root = i;
            continue;
        }
        gp[i].push_back(--x);
        gp[x].push_back(i);
    }

    for (int i = 0; i < n; i++)sub[i] = i;
    dfss(root, root);

    for (int i = 0; i < n; i++) sort(begin(gp[i]), end(gp[i]), cm);
    order(root, -1);
    build(root, -1);

    set<pair<int, int>>st;
    for (int i = 0; i < n; i++) st.insert({ i,qth[i] });

    while (q--) {
        int t, k; cin >> t >> k;
        if (t == 1) {
            int res;
            while (k--) {
                pair<int, int>c = *st.begin();
                st.erase(st.begin());
                black[c.second] = true;
                res = c.second;
            }
            cout << res + 1 << endl;
            continue;
        }
        vector<int>c = get(k - 1);
        st.insert({ rqth[c[0]], c[0] });
        black[c[0]] = false;
        cout << c[1] << endl;
    }
}

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