Submission #1124104

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124104		adaawf	Ball Machine (BOI13_ballmachine)	C++20	21.83 / 100	162 ms	24300 KiB

ballmachine

#include <iostream>
#include <set>
#include <vector>
using namespace std;
set<int> s[100005];
int l[100005][18], da[100005], f[100005], h;
void dfs(int x, int fl) {
    if (fl == 1) {
        h = x;
    }
    f[x] = x;
    if (s[x].empty()) return;
    for (int w : s[x]) {
        dfs(w, (w == *s[x].begin()));
        if (w == *s[x].begin()) f[x] = f[w];
    }
}
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;
        s[x].insert(i);
    }
    dfs(0, 1);
    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(h);
                if (!s[l[h][0]].empty()) {
                    int k = *s[l[h][0]].begin();
                    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(x);
            h = x;
            da[h] = 0;
            cout << res << '\n';
        }
    }
}

• Subtask 1: 0 / 25
• Subtask 2: 6.4286 / 30
• Subtask 3: 14.2857 / 40
• Subtask 4: 1.1111 / 5