제출 #872754

#제출 시각아이디문제언어결과실행 시간메모리
872754vjudge1Ball Machine (BOI13_ballmachine)C++17
100 / 100
673 ms38908 KiB
#include<bits/stdc++.h> using namespace std; #define F first #define S second #define pii pair<int, int> #define pb push_back #define pp pop_back #define all(x) x.begin(), x.end() const int N = 1e5 + 12, M = 20; vector<int> g[N]; int n, q, t, f[N], p[N], par[M][N], root, d[N], seg[4 * N], lazy[4 * N], ls[4 * N], h[N]; pii pl[4 * N]; void ip() { cin >> n >> q; for (int i = 0; i < n; i++) { int u; cin >> u; u--; par[0][i] = u; if (u == -1) root = i; else { g[u].pb(i); g[i].pb(u); } } par[0][root] = root; } void dfs1(int u) { d[u] = u; for (auto i: g[u]) if (i != par[0][u]) { h[i] = h[u] + 1; dfs1(i); d[u] = min(d[u], d[i]); } } void dfs2(int u) { vector<pii> tmp; for (auto i: g[u]) if (i != par[0][u]) tmp.pb({d[i], i}); sort(all(tmp)); for (auto i: tmp) dfs2(i.S); f[t] = u; p[u] = t; t++; } void pre() { dfs1(root); dfs2(root); for (int i = 1; i < M; i++) for (int j = 0; j < n; j++) par[i][j] = par[i - 1][par[i - 1][j]]; } void shift(int id) { if (ls[id * 2] < ls[id]) { seg[id * 2] = lazy[id] * (pl[id * 2].S - pl[id * 2].F); lazy[id * 2] = lazy[id]; ls[id * 2] = ls[id]; } if (ls[id * 2 + 1] < ls[id]) { lazy[id * 2 + 1] = lazy[id]; seg[id * 2 + 1] = lazy[id] * (pl[id * 2 + 1].S - pl[id * 2 + 1].F); ls[id * 2 + 1] = ls[id]; } } void add(int l, int r, int x, int w, int id = 1) { if (l <= pl[id].F && r >= pl[id].S) { lazy[id] = x; seg[id] = x * (pl[id].S - pl[id].F); ls[id] = w; return; } if (r <= pl[id].F || l >= pl[id].S) return; shift(id); add(l, r, x, w, id * 2); add(l, r, x, w, id * 2 + 1); seg[id] = seg[id * 2] + seg[id * 2 + 1]; } int ask(int l, int r, int id = 1) { if (l <= pl[id].F && r >= pl[id].S) return seg[id]; if (r <= pl[id].F || l >= pl[id].S) return 0; shift(id); int res = ask(l, r, id * 2) + ask(l, r, id * 2 + 1); seg[id] = seg[id * 2] + seg[id * 2 + 1]; return res; } void query() { int w = 1; pl[1] = {0, n}; for (int i = 1; i < 2 * n; i++) { int mid = (pl[i].F + pl[i].S) / 2; pl[i * 2] = {pl[i].F, mid}; pl[i * 2 + 1] = {mid, pl[i].S}; } while (q--) { int u, v; cin >> u >> v; if (u == 1) { int l = -1, r = n; while (r - l > 1) { int mid = (l + r) / 2; if (mid + 1 - ask(0, mid + 1) < v) l = mid; else r = mid; } cout << f[r] + 1 << '\n'; add(0, r + 1, 1, w++); } else { v--; int z = v; for (int i = M - 1; ~i; i--) if (ask(p[par[i][v]], p[par[i][v]] + 1)) v = par[i][v]; cout << h[z] - h[v] << '\n'; add(p[v], p[v] + 1, 0, w++); } } } int32_t main() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); ip(), pre(), query(); 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...