Submission #708476

#	Time	Username	Problem	Language	Result	Execution time	Memory
708476		stevancv	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	338 ms	27964 KiB

ballmachine

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 5;
const ll linf = 1e18;
const int mod = 1e9 + 7;
vector<int> g[N];
int lift[N][17], mn[N], order[N], out[N], tsz;
void Dfs(int s, int e) {
    mn[s] = s;
    lift[s][0] = e;
    for (int i = 1; i < 17; i++) lift[s][i] = lift[lift[s][i - 1]][i - 1];
    for (int u : g[s]) {
        if (u != e) {
            Dfs(u, s);
            smin(mn[s], mn[u]);
        }
    }
}
void Dfs1(int s, int e) {
    for (int u : g[s]) {
        if (u != e) {
            Dfs1(u, s);
        }
    }
    out[s] = ++tsz;
    order[tsz] = s;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q;
    cin >> n >> q;
    int root = 0;
    for (int i = 1; i <= n; i++) {
        int x; cin >> x;
        if (x == 0) root = i;
        else g[x].push_back(i);
    }
    Dfs(root, 0);
    for (int i = 1; i <= n; i++) {
        sort(g[i].begin(), g[i].end(), [&] (int xx, int yy) {
            return mn[xx] < mn[yy];
        });
    }
    Dfs1(root, 0);
    set<int> s;
    for (int i = 1; i <= n; i++) s.insert(i);
    while (q--) {
        int ty, x;
        cin >> ty >> x;
        if (ty == 1) {
            int res = -1;
            while (x--) {
                res = *s.begin();
                s.erase(res);
            }
            cout << order[res] << en;
            continue;
        }
        int ans = 0;
        for (int i = 16; i >= 0; i--) {
            int who = lift[x][i];
            if (s.find(out[who]) == s.end() && who > 0) {
                ans += 1 << i;
                x = who;
            }
        }
        s.insert(out[x]);
        cout << ans << en;
    }
    return 0;
}

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