| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 695389 | Duy_e | Ball Machine (BOI13_ballmachine) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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], up[20][N];
vector <int> d[N], order;
void dfs(int u) {
mi[u] = u;
for (int v: d[u])
dfs(v), mi[u] = min(mi[u], mi[v]);
}
void dfs2(int u) {
for (int v: d[u]) dfs2(v);
order.push_back(u);
}
priority_queue <pii, vector <pii>, greater <pii>> st;
void del(int u) {
int cnt = 0;
rrep(i, 19, 0) if (full[up[i][u]])
u = up[i][u], cnt += 1 << i;
full[u] = false;
st.push({mi[u], u});
cout << cnt << '\n';
}
int cur = 0;
void add(int k) {
int lst = 0;
while (st.size() && k) {
lst = st.top().nd;
st.pop();
k --;
full[lst] = true;
}
while (k) k --, lst = order[cur ++], full[lst] = true;
cout << lst << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen("A.ans", "w", stdout);
cin >> n >> q;
rep(i, 1, n) {
int p; cin >> p;
d[p].push_back(i);
up[0][i] = p;
}
dfs(0);
rep(i, 1, 19) rep(j, 1, n)
up[i][j] = up[i - 1][up[i - 1][j]];
auto cmp = [&] (int u, int v) { return mi[u] < mi[v]; };
rep(i, 1, n) sort(d[i].begin(), d[i].end(), cmp);
dfs2(0);
int t, x;
while (q --) {
cin >> t >> x;
if (t == 1) add(x);
if (t == 2) del(x);
}
return 0;
}