Submission #872049

#TimeUsernameProblemLanguageResultExecution timeMemory
872049vjudge1Ball Machine (BOI13_ballmachine)C++17
64.14 / 100
459 ms26568 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...