Submission #695372

#	Time	Username	Problem	Language	Result	Execution time	Memory
695372		Duy_e	Ball Machine (BOI13_ballmachine)	C++14	47.14 / 100	1097 ms	15852 KiB

ballmachine

#include <bits/stdc++.h>
#define ll long long
#define rep(i, n, m) for (ll i = n; i <= m; i ++)
#define rrep(i, n, m) for (ll i = n; i >= m; i --)
using namespace std;
const long long N = 2e5 + 5;
int n, q, a[N], full[N], mi[N], par[N];
vector <int> d[N];

void dfs(int u) {
    mi[u] = u;
    for (int v: d[u])
        dfs(v), mi[u] = min(mi[u], mi[v]);
}

int DFS(int u, int &k) {
    int lst = 0;
    for (int v: d[u]) if (!full[v] && k)
        lst = DFS(v, k);

    if (k) {
        full[u] = true;
        k --;
        return u;
    }
    return lst;
}

void del(int u) {
    int cnt = 0;
    while (full[par[u]]) {
        cnt ++;
        u = par[u];
    }
    full[u] = false;
    cout << cnt << '\n';
}

void add(int k) {
    cout << DFS(0, k) << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    //freopen("A.inp", "r", stdin);
    //freopen("A.out", "w", stdout);

    cin >> n >> q;
    rep(i, 1, n) {
        int p; cin >> p;
        d[p].push_back(i);
        par[i] = p;
    }

    dfs(0);

    auto cmp = [&] (int u, int v) { return mi[u] < mi[v]; };
    rep(i, 1, n) sort(d[i].begin(), d[i].end(), cmp);

    int t, x;

    while (q --) {
        cin >> t >> x;
        if (t == 1) add(x);
        if (t == 2) del(x);
    }

    return 0;
}

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