#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1e5+5;
const int INV = -1;
int N, Q;
vector<int> adj[maxn];
struct Node {
int s, e, m;
//covers s,e;
int sum;
int lazy;
Node *l, *r;
Node(int a, int b) {
s = a;
e = b;
sum = 0;
lazy = INV;
if (s != e) {
m = (s+e)/2;
l = new Node(s,m);
r = new Node(m+1,e);
sum = l->sum + r->sum;
}
else {
l = NULL;
r = NULL;
sum = 1;
}
}
void push() {
if (lazy == INV) return;
if (s != e) {
l->lazy = lazy;
l->sum = (l->e - l->s + 1) * lazy;
r->lazy = lazy;
r->sum = (r->e - r->s + 1) * lazy;
}
lazy = INV;
}
void pull() {
sum = l->sum + r->sum;
}
void add(int st, int en, int x) {
//lazy: already accounted for in your own node, not the childs nodes
if (st <= s && e <= en) {
lazy = x;
sum = (e - s + 1) * x;
return;
}
push();
if (st <= m) {
l->add(st,en,x);
}
if (en > m) {
r->add(st,en,x);
}
pull();
}
int find(int k) {
push();
//cout << s << ' ' << e << '\n';
if (s == e) return s;
if (l->sum >= k) {
return l->find(k);
}
return r->find(k-l->sum);
}
int getsum(int st, int en) {
push();
//if completely included
if (st <= s && e <= en) {
return sum;
}
int ret = 0;
if (st <= m) {
ret += l->getsum(st,en);
}
if (en > m) {
ret += r->getsum(st,en);
}
return ret;
}
};
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 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);
Node *root = new Node(1,N);
while (Q--) {
int t; cin >> t;
if (t == 1) {
int k; cin >> k;
int r = root->find(k);
root->add(1,r,0);
cout << inv[r] << '\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 (root->getsum(ord[nxt],ord[nxt]) == 0) {
res += (1<<k);
v = nxt;
}
}
root->add(ord[v],ord[v],1); //set it to empty
cout << res << '\n';
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
2936 KB |
Output isn't correct |
2 |
Incorrect |
212 ms |
16396 KB |
Output isn't correct |
3 |
Incorrect |
107 ms |
16404 KB |
Output isn't correct |
4 |
Incorrect |
4 ms |
2808 KB |
Output isn't correct |
5 |
Incorrect |
4 ms |
2808 KB |
Output isn't correct |
6 |
Incorrect |
5 ms |
2936 KB |
Output isn't correct |
7 |
Incorrect |
5 ms |
3064 KB |
Output isn't correct |
8 |
Incorrect |
6 ms |
3064 KB |
Output isn't correct |
9 |
Incorrect |
14 ms |
3636 KB |
Output isn't correct |
10 |
Incorrect |
37 ms |
6136 KB |
Output isn't correct |
11 |
Incorrect |
225 ms |
16456 KB |
Output isn't correct |
12 |
Incorrect |
115 ms |
16376 KB |
Output isn't correct |
13 |
Incorrect |
186 ms |
16476 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
78 ms |
8184 KB |
Output is correct |
2 |
Incorrect |
671 ms |
26160 KB |
Output isn't correct |
3 |
Incorrect |
117 ms |
22644 KB |
Output isn't correct |
4 |
Incorrect |
179 ms |
10332 KB |
Output isn't correct |
5 |
Incorrect |
309 ms |
10196 KB |
Output isn't correct |
6 |
Incorrect |
293 ms |
10268 KB |
Output isn't correct |
7 |
Incorrect |
288 ms |
9336 KB |
Output isn't correct |
8 |
Correct |
81 ms |
8184 KB |
Output is correct |
9 |
Incorrect |
436 ms |
26224 KB |
Output isn't correct |
10 |
Incorrect |
547 ms |
25976 KB |
Output isn't correct |
11 |
Incorrect |
388 ms |
25864 KB |
Output isn't correct |
12 |
Incorrect |
493 ms |
24312 KB |
Output isn't correct |
13 |
Correct |
159 ms |
26452 KB |
Output is correct |
14 |
Incorrect |
100 ms |
22644 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
169 ms |
14584 KB |
Output isn't correct |
2 |
Incorrect |
663 ms |
24804 KB |
Output isn't correct |
3 |
Correct |
440 ms |
24044 KB |
Output is correct |
4 |
Incorrect |
261 ms |
21472 KB |
Output isn't correct |
5 |
Incorrect |
383 ms |
21180 KB |
Output isn't correct |
6 |
Incorrect |
367 ms |
21368 KB |
Output isn't correct |
7 |
Incorrect |
351 ms |
20216 KB |
Output isn't correct |
8 |
Correct |
349 ms |
24032 KB |
Output is correct |
9 |
Incorrect |
408 ms |
26348 KB |
Output isn't correct |
10 |
Incorrect |
838 ms |
25996 KB |
Output isn't correct |
11 |
Incorrect |
619 ms |
25976 KB |
Output isn't correct |
12 |
Incorrect |
613 ms |
24880 KB |
Output isn't correct |
13 |
Correct |
567 ms |
29756 KB |
Output is correct |
14 |
Incorrect |
203 ms |
22936 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
497 ms |
26464 KB |
Output isn't correct |
2 |
Incorrect |
621 ms |
24924 KB |
Output isn't correct |
3 |
Correct |
189 ms |
29292 KB |
Output is correct |
4 |
Incorrect |
525 ms |
26488 KB |
Output isn't correct |
5 |
Incorrect |
636 ms |
26104 KB |
Output isn't correct |
6 |
Incorrect |
456 ms |
26008 KB |
Output isn't correct |
7 |
Incorrect |
580 ms |
24696 KB |
Output isn't correct |
8 |
Correct |
173 ms |
29304 KB |
Output is correct |
9 |
Incorrect |
118 ms |
22704 KB |
Output isn't correct |