#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5+5;
int N, Q;
vector<int> adj[maxn];
int minsub[maxn];
int ord[maxn], inv[maxn]; //node to seg, seg to node
int pt = 1;
void prep(int i) {
minsub[i] = i;
for (int j: adj[i]) {
minsub[i] = min(minsub[i],minsub[j]);
}
sort(adj[i].begin(),adj[i].end(),[](int a, int b) {
return minsub[a] < minsub[b];
});
}
void dfs(int i) {
for (int j: adj[i]) {
dfs(j);
}
ord[i] = pt;
inv[pt] = i;
pt++;
//cout << i << ' ';
}
const int maxk = 18;
int par[maxk][maxn];
int seg[maxn];
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> N >> Q;
int rt = -1;
for (int i = 1; i <= N; i++) {
int pi; cin >> pi;
if (pi == 0) rt = i;
else adj[pi].push_back(i);
par[0][i] = pi;
}
for (int k = 1; k < maxk; k++) {
for (int i = 1; i <= N; i++) {
par[k][i] = par[k-1][par[k-1][i]];
}
}
prep(rt);
dfs(rt);
while (Q--) {
int t; cin >> t;
if (t == 1) {
int k; cin >> k;
for (int i = 1; i <= k; i++) {
seg[inv[i]] = 1;
}
cout << inv[k] << '\n';
}
else {
int v; cin >> v;
int res = 0;
for (int k = maxk - 1; k >= 0; k--) {
if (par[k][v] == 0) continue;
int nxt = par[k][v];
if (seg[nxt] == 1) {
res += (1<<k);
v = nxt;
}
}
seg[v] = 0;
cout << res << '\n';
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
2808 KB |
Output isn't correct |
2 |
Incorrect |
87 ms |
9464 KB |
Output isn't correct |
3 |
Incorrect |
52 ms |
9208 KB |
Output isn't correct |
4 |
Incorrect |
4 ms |
2808 KB |
Output isn't correct |
5 |
Incorrect |
5 ms |
2808 KB |
Output isn't correct |
6 |
Incorrect |
4 ms |
2808 KB |
Output isn't correct |
7 |
Incorrect |
4 ms |
2936 KB |
Output isn't correct |
8 |
Incorrect |
4 ms |
2940 KB |
Output isn't correct |
9 |
Incorrect |
8 ms |
3192 KB |
Output isn't correct |
10 |
Incorrect |
16 ms |
4472 KB |
Output isn't correct |
11 |
Incorrect |
67 ms |
9464 KB |
Output isn't correct |
12 |
Incorrect |
52 ms |
9208 KB |
Output isn't correct |
13 |
Incorrect |
63 ms |
9436 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
5852 KB |
Output is correct |
2 |
Incorrect |
97 ms |
15452 KB |
Output isn't correct |
3 |
Incorrect |
59 ms |
12276 KB |
Output isn't correct |
4 |
Incorrect |
48 ms |
6776 KB |
Output isn't correct |
5 |
Incorrect |
44 ms |
6648 KB |
Output isn't correct |
6 |
Incorrect |
43 ms |
6708 KB |
Output isn't correct |
7 |
Incorrect |
43 ms |
6136 KB |
Output isn't correct |
8 |
Correct |
31 ms |
5880 KB |
Output is correct |
9 |
Incorrect |
143 ms |
15836 KB |
Output isn't correct |
10 |
Incorrect |
102 ms |
15372 KB |
Output isn't correct |
11 |
Incorrect |
93 ms |
15608 KB |
Output isn't correct |
12 |
Incorrect |
102 ms |
14028 KB |
Output isn't correct |
13 |
Correct |
78 ms |
17016 KB |
Output is correct |
14 |
Incorrect |
60 ms |
12404 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
52 ms |
9344 KB |
Output isn't correct |
2 |
Incorrect |
116 ms |
14416 KB |
Output isn't correct |
3 |
Correct |
92 ms |
16036 KB |
Output is correct |
4 |
Incorrect |
78 ms |
13304 KB |
Output isn't correct |
5 |
Incorrect |
74 ms |
13048 KB |
Output isn't correct |
6 |
Incorrect |
92 ms |
12920 KB |
Output isn't correct |
7 |
Incorrect |
78 ms |
12024 KB |
Output isn't correct |
8 |
Correct |
94 ms |
15992 KB |
Output is correct |
9 |
Incorrect |
119 ms |
16120 KB |
Output isn't correct |
10 |
Incorrect |
123 ms |
15608 KB |
Output isn't correct |
11 |
Incorrect |
123 ms |
15608 KB |
Output isn't correct |
12 |
Incorrect |
119 ms |
14364 KB |
Output isn't correct |
13 |
Correct |
160 ms |
19320 KB |
Output is correct |
14 |
Incorrect |
92 ms |
12532 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
120 ms |
15932 KB |
Output isn't correct |
2 |
Incorrect |
118 ms |
14292 KB |
Output isn't correct |
3 |
Correct |
93 ms |
18812 KB |
Output is correct |
4 |
Incorrect |
111 ms |
15864 KB |
Output isn't correct |
5 |
Incorrect |
113 ms |
15500 KB |
Output isn't correct |
6 |
Incorrect |
100 ms |
15480 KB |
Output isn't correct |
7 |
Incorrect |
146 ms |
14480 KB |
Output isn't correct |
8 |
Correct |
109 ms |
18860 KB |
Output is correct |
9 |
Incorrect |
72 ms |
12300 KB |
Output isn't correct |