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>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define len(x) (int) x.size()
#define pb push_back
mt19937 rnd(time(0));
const int N = 1e5 + 7, LG = 19;
int n, q, rt, place[N], h[N], mn[N], par[LG][N];
int seg[N << 2], lazy[N << 2];
vector<int> adj[N], ord;
void read_input() {
cin >> n >> q;
for (int i = 0; i < n; i++) {
int par;
cin >> par;
if (!par)
rt = i;
else
adj[--par].pb(i);
}
}
int k_par(int u, int k) {
for (int i = 0; i < LG; i++)
if ((k >> i) & 1)
u = par[i][u];
return u;
}
void dfs_mn(int u) {
mn[u] = u;
for (int v: adj[u]) {
par[0][v] = u;
h[v] = 1 + h[u];
dfs_mn(v);
mn[u] = min(mn[u], mn[v]);
}
sort(all(adj[u]), [] (int i, int j) {
return mn[i] < mn[j];
});
}
void dfs_ord(int u) {
for (int v: adj[u])
dfs_ord(v);
ord.pb(u);
}
void shift(int id, int st, int mid, int en) {
if (!lazy[id])
return;
int lc = id << 1, rc = lc | 1;
seg[lc] = mid - st, lazy[lc] = true;
seg[rc] = mid - en, lazy[rc] = true;
lazy[id] = 0;
}
void upd(int l, int r, bool b, int id = 1, int st = 0, int en = n) {
if (r <= st || l >= en)
return;
if (st >= l && en <= r) {
if (b) {
seg[id] = en - st;
lazy[id] = true;
}
else
seg[id] = 0;
return;
}
int mid = (st + en) >> 1, lc = id << 1, rc = lc | 1;
shift(id, st, mid, en);
upd(l, r, b, lc, st, mid), upd(l, r, b, rc, mid, en);
seg[id] = seg[lc] + seg[rc];
}
int get(int p, int id = 1, int st = 0, int en = n) {
if (en - st == 1)
return seg[id];
int mid = (st + en) >> 1, lc = id << 1, rc = lc | 1;
shift(id, st, mid, en);
if (p < mid)
return get(p, lc, st, mid);
return get(p, rc, mid, en);
}
int find_k(int k, int id = 1, int st = 0, int en = n) {
if (en - st == 1)
return st;
int lc = id << 1, rc = lc | 1;
int mid = (st + en) >> 1;
shift(id, st, mid, en);
if (mid - st - seg[lc] >= k)
return find_k(k, lc, st, mid);
return find_k(k - (mid - st - seg[lc]), rc, mid, en);
}
void solve() {
dfs_mn(rt);
dfs_ord(rt);
for (int i = 0; i < n; i++)
place[ord[i]] = i;
par[0][rt] = rt;
for (int i = 1; i < LG; i++)
for (int j = 0; j < n; j++)
par[i][j] = par[i - 1][par[i - 1][j]];
while (q--) {
int type;
cin >> type;
if (type == 1) {
int k;
cin >> k;
int t = find_k(k);
upd(0, t + 1, 1);
cout << ord[t] + 1 << '\n';
}
else {
int u;
cin >> u;
u--;
upd(place[u], place[u] + 1, 0);
if (!get(place[par[0][u]])) {
cout << 0 << '\n';
continue;
}
int l = 1, r = h[u] + 1;
while (r - l > 1) {
int mid = (l + r) / 2;
if (get(place[k_par(u, mid)]))
l = mid;
else
r = mid;
}
int v = k_par(u, l);
upd(place[v], place[v] + 1, 0);
upd(place[u], place[u] + 1, 1);
cout << h[u] - h[v] << '\n';
}
}
}
int32_t main() {
ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
read_input(), solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |