// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define pb push_back
#define pf push_front
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
using db = long double;
template<class T> using pq = priority_queue<T, V<T>, greater<T>>;
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 19;
int main() {
cin.tie(0)->sync_with_stdio(0);
int N, Q; cin >> N >> Q;
int R = -1;
vi P(N);
V<vi> chd(N); for(int i = 0; i < N; i++) {
int p; cin >> p; --p;
if (p != -1) chd[p].pb(i), P[i] = p;
else R = i, P[i] = -1;
}
vi mn(N, MOD), dep(N);
V<vi> up(N, vi(LG));
function<void(int)> gen = [&](int u) {
for(int i = 1; i < LG; i++) up[u][i] = up[up[u][i-1]][i-1];
mn[u] = u;
for(auto& v : chd[u]) {
up[v][0] = u; dep[v] = dep[u] + 1; gen(v);
mn[u] = min(mn[v], mn[u]);
}
};
up[R][0] = R, dep[R] = 0; gen(R);
vi deg(N); for(int i = 0; i < N; i++) deg[i] = sz(chd[i]);
vi ord(N);
pq<pi> q; for(int i = 0; i < N; i++) if (deg[i] == 0) {
q.push(mp(mn[i], i));
}
int cur = 0;
while(sz(q)) {
int u = q.top().s; q.pop();
// cout << u << " " << cur << endl;
ord[u] = cur++;
if (P[u] != -1) {
// cout << P[u] << endl;
// cout << deg[P[u]] << endl;
deg[P[u]]--;
if (deg[P[u]] == 0) q.push(mp(mn[P[u]], P[u]));
}
}
pq<pi> W; for(int i = 0; i < N; i++) W.push(mp(ord[i], i));
vi C(N); // C[i] = 0 (off) / 1 (on)
for(int t = 0; t < Q; t++) {
int type; cin >> type;
if (type == 1) {
int k; cin >> k;
int lst = -1;
while(k--) {
assert(sz(W));
int u = W.top().s; W.pop();
C[u] = 1; lst = u;
}
cout << lst + 1 << nl;
} else {
int u; cin >> u; --u;
int d = dep[u]; assert(C[u] == 1);
for(int i = LG-1; i >= 0; i--) {
if (C[up[u][i]]) u = up[u][i];
}
C[u] = 0; W.push(mp(ord[u], u));
cout << d - dep[u] << nl;
}
}
exit(0-0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 2 |
Runtime error |
58 ms |
26704 KB |
Execution killed with signal 6 |
| 3 |
Runtime error |
41 ms |
26708 KB |
Execution killed with signal 6 |
| 4 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 5 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 6 |
| 6 |
Runtime error |
1 ms |
856 KB |
Execution killed with signal 6 |
| 7 |
Runtime error |
1 ms |
860 KB |
Execution killed with signal 6 |
| 8 |
Runtime error |
1 ms |
856 KB |
Execution killed with signal 6 |
| 9 |
Runtime error |
3 ms |
2140 KB |
Execution killed with signal 6 |
| 10 |
Runtime error |
11 ms |
7256 KB |
Execution killed with signal 6 |
| 11 |
Runtime error |
52 ms |
26696 KB |
Execution killed with signal 6 |
| 12 |
Runtime error |
48 ms |
26696 KB |
Execution killed with signal 6 |
| 13 |
Runtime error |
43 ms |
26568 KB |
Execution killed with signal 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
6356 KB |
Output is correct |
| 2 |
Runtime error |
95 ms |
48660 KB |
Execution killed with signal 6 |
| 3 |
Correct |
66 ms |
20680 KB |
Output is correct |
| 4 |
Runtime error |
21 ms |
15376 KB |
Execution killed with signal 6 |
| 5 |
Runtime error |
21 ms |
15052 KB |
Execution killed with signal 6 |
| 6 |
Runtime error |
20 ms |
15060 KB |
Execution killed with signal 6 |
| 7 |
Runtime error |
18 ms |
12920 KB |
Execution killed with signal 6 |
| 8 |
Correct |
23 ms |
6348 KB |
Output is correct |
| 9 |
Runtime error |
91 ms |
49204 KB |
Execution killed with signal 6 |
| 10 |
Runtime error |
102 ms |
48524 KB |
Execution killed with signal 6 |
| 11 |
Runtime error |
97 ms |
48716 KB |
Execution killed with signal 6 |
| 12 |
Runtime error |
109 ms |
44120 KB |
Execution killed with signal 6 |
| 13 |
Correct |
84 ms |
26776 KB |
Output is correct |
| 14 |
Correct |
61 ms |
20604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
45 ms |
25288 KB |
Execution killed with signal 6 |
| 2 |
Runtime error |
96 ms |
44624 KB |
Execution killed with signal 6 |
| 3 |
Correct |
100 ms |
24260 KB |
Output is correct |
| 4 |
Runtime error |
71 ms |
39592 KB |
Execution killed with signal 6 |
| 5 |
Runtime error |
76 ms |
39160 KB |
Execution killed with signal 6 |
| 6 |
Runtime error |
74 ms |
39236 KB |
Execution killed with signal 6 |
| 7 |
Runtime error |
69 ms |
35908 KB |
Execution killed with signal 6 |
| 8 |
Correct |
106 ms |
24208 KB |
Output is correct |
| 9 |
Runtime error |
132 ms |
50288 KB |
Execution killed with signal 6 |
| 10 |
Runtime error |
139 ms |
49488 KB |
Execution killed with signal 6 |
| 11 |
Runtime error |
125 ms |
49004 KB |
Execution killed with signal 6 |
| 12 |
Runtime error |
105 ms |
44628 KB |
Execution killed with signal 6 |
| 13 |
Correct |
156 ms |
30408 KB |
Output is correct |
| 14 |
Runtime error |
74 ms |
40260 KB |
Execution killed with signal 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
91 ms |
49224 KB |
Execution killed with signal 6 |
| 2 |
Runtime error |
108 ms |
44624 KB |
Execution killed with signal 6 |
| 3 |
Correct |
102 ms |
30152 KB |
Output is correct |
| 4 |
Runtime error |
92 ms |
49196 KB |
Execution killed with signal 6 |
| 5 |
Runtime error |
106 ms |
48776 KB |
Execution killed with signal 6 |
| 6 |
Runtime error |
109 ms |
48696 KB |
Execution killed with signal 6 |
| 7 |
Runtime error |
109 ms |
44696 KB |
Execution killed with signal 6 |
| 8 |
Correct |
119 ms |
30060 KB |
Output is correct |
| 9 |
Correct |
73 ms |
20672 KB |
Output is correct |
