Submission #870235

#TimeUsernameProblemLanguageResultExecution timeMemory
870235falazBall Machine (BOI13_ballmachine)C++17
100 / 100
164 ms36808 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define endl '\n' #define F first #define S second const int N = 1e5 + 15, LOG = 19; int n, q, par[LOG][N], zr[N], sv[N], t = 1, root; unordered_map<int, int> mp; vector<int> adj[N]; bool ch[N]; set<int> s; void ip() { cin >> n >> q; for (int i = 1; i <= n; i++) { zr[i] = i; int p; cin >> p; par[0][i] = p; adj[p].push_back(i); if (p == 0) root = i; } } void fix_par() { for (int j = 1; j < LOG; j++) for (int i = 1; i <= n; i++) par[j][i] = par[j - 1][par[j - 1][i]]; } void dfs(int v) { for (auto u : adj[v]) { dfs(u); zr[v] = min(zr[v], zr[u]); } } void fdfs(int v) { for (auto u : adj[v]) fdfs(u); sv[v] = t; mp[t] = v; s.insert(t); t++; } bool cmp(int i, int j) { return (zr[i] < zr[j]); } void fix() { for (int i = 1; i <= n; i++) sort(adj[i].begin(), adj[i].end(), cmp); /* for (int i = 1; i <= n; i++) { cout << i << " : "; for (auto v : adj[i]) cout << v << " "; cout << endl; }*/ } pair<int, int> get_par(int v) { int cnt = 0; for (int i = LOG - 1; ~i; i--) { if (ch[par[i][v]]) { cnt += (1 << i); v = par[i][v]; } } return (make_pair(cnt, v)); } void query() { while (q--) { int qu, f; cin >> qu; if (qu == 1) { cin >> f; int v; while (f--) { v = mp[*s.begin()]; s.erase(s.begin()); ch[v] = true; // cout << v << " "; } // cout << endl; cout << v << endl; } else { cin >> f; pair<int, int> ans = get_par(f); // cout << ans.F << " " << ans.S << endl; ch[ans.S] = false; s.insert(sv[ans.S]); cout << ans.F << endl; } } } void run() { ip(); fix_par(); dfs(root); fix(); fdfs(root); query(); } signed main() { ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); run(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...