Submission #1124107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124107		adaawf	Ball Machine (BOI13_ballmachine)	C++20	60.29 / 100	135 ms	33456 KiB

ballmachine

#include <iostream>
#include <set>
#include <vector>
using namespace std;
set<pair<int, int>> s[100005];
vector<int> g[100005];
int l[100005][18], da[100005], d[100005], f[100005], h;
void dfs(int x) {
    d[x] = x;
    for (int w : g[x]) {
        dfs(w);
        d[x] = min(d[x], d[w]);
    }
}
void dfs2(int x) {
    f[x] = x;
    for (int w : g[x]) s[x].insert({d[w], w});
    for (auto w : s[x]) {
        dfs2(w.second);
        if (w.first == (*s[x].begin()).first) f[x] = f[w.second];
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        l[i][0] = x;
        g[x].push_back(i);
    }
    dfs(0);
    dfs2(0);
    h = f[0];
    for (int i = 1; i <= 17; i++) {
        for (int j = 1; j <= n; j++) {
            l[j][i] = l[l[j][i - 1]][i - 1];
        }
    }
    for (int jj = 0; jj < q; jj++) {
        int w, x;
        cin >> w >> x;
        if (w == 1) {
            int res = 0;
            for (int i = 1; i <= x; i++) {
                res = h;
                da[h] = 1;
                s[l[h][0]].erase({d[h], h});
                if (!s[l[h][0]].empty()) {
                    int k = (*s[l[h][0]].begin()).second;
                    h = f[k];
                }
                else h = l[h][0];
            }
            cout << res << '\n';
        }
        else {
            int res = 0;
            for (int i = 17; i >= 0; i--) {
                if (da[l[x][i]] == 1) {
                    x = l[x][i];
                    res += (1 << i);
                }
            }
            s[l[x][0]].insert({d[x], x});
            h = x;
            da[h] = 0;
            cout << res << '\n';
        }
    }
}

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