Submission #695373

#TimeUsernameProblemLanguageResultExecution timeMemory
695373Duy_eBall Machine (BOI13_ballmachine)C++14
85.48 / 100
1089 ms24044 KiB
#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]; void dfs(int u) { mi[u] = u; for (int v: d[u]) dfs(v), mi[u] = min(mi[u], mi[v]); } int DFS(int u, int &k) { int lst = 0; for (int v: d[u]) if (!full[v] && k) lst = DFS(v, k); if (k) { full[u] = true; k --; return u; } return lst; } 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; cout << cnt << '\n'; } void add(int k) { cout << DFS(0, k) << '\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); int t, x; while (q --) { cin >> t >> x; if (t == 1) add(x); if (t == 2) del(x); } 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...