#include <bits/stdc++.h>
#define loop(a, b) for(int a = 0; a < b; ++a)
#define loop1(a, b) for(int a = 1; a <= b; ++a)
#define loopc(a, c, b) for(int a = c; a < b; ++a)
#define loopr(a, b) for(int a = b-1; a >= 0; --a)
#define mp make_pair
using namespace std;
typedef priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pair_queue;
int nn, qq, q, v;
vector<int> tree[100001];
int par[20][100001], sub[100001];
map<int, int> order;
pair_queue que;
bool val[100001];
void dfsdep(int n) {
int s = n;
loop(a, tree[n].size()) {
dfsdep(tree[n][a]);
s = min(s, tree[n][a]);
}
sub[n] = s;
}
bool ord(const int &a, const int &b) {
return sub[a] < sub[b];
}
void dfsord(int n) {
sort(tree[n].begin(), tree[n].end(), ord);
loop(a, tree[n].size()) {
dfsord(tree[n][a]);
}
order[n] = que.size();
que.push(mp(order[n], n));
}
int main() {
cin >> nn >> qq;
loop1(a, nn) {
cin >> par[0][a];
tree[par[0][a]].push_back(a);
}
loop1(a, 18) {
loop1(b, nn) {
par[a][b] = par[a-1][par[a-1][b]];
}
}
/*loop(a, 18) {
loop1(b, nn) {
cout << par[a][b] << " " ;
}
cout << endl;
}*/
dfsdep(0);
dfsord(0);
/*loop1(a, nn) {
cout << order[a] << endl;
}*/
//cout << endl;
pair<int, int> vv;
int dd, pp;
loop(w, qq) {
cin >> q >> v;
if (q==1) {
while (v--) {
vv = que.top();
val[vv.second] = true;
que.pop();
}
cout << vv.second << endl;
}
else if (q==2) {
pp = v;
dd = 0;
loopr(a, 18) {
//cout <<pp << " " << dd << " " << a << endl;
//cout << par[a][pp] << endl << endl;;
if (val[par[a][pp]]) {
pp = par[a][pp];
dd += 1<<a;
}
}
val[pp] = false;
//cout <<pp << " " << dd << endl;
cout << dd << endl;
}
/*loop1(a, nn) {
cout << val[a] << " ";
}
cout << endl;*/
}
return 0;
}
Compilation message
ballmachine.cpp: In function 'void dfsdep(int)':
ballmachine.cpp:2:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
2 | #define loop(a, b) for(int a = 0; a < b; ++a)
......
22 | loop(a, tree[n].size()) {
| ~~~~~~~~~~~~~~~~~
ballmachine.cpp:22:5: note: in expansion of macro 'loop'
22 | loop(a, tree[n].size()) {
| ^~~~
ballmachine.cpp: In function 'void dfsord(int)':
ballmachine.cpp:2:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
2 | #define loop(a, b) for(int a = 0; a < b; ++a)
......
35 | loop(a, tree[n].size()) {
| ~~~~~~~~~~~~~~~~~
ballmachine.cpp:35:5: note: in expansion of macro 'loop'
35 | loop(a, tree[n].size()) {
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
2816 KB |
Output isn't correct |
2 |
Incorrect |
450 ms |
14060 KB |
Output isn't correct |
3 |
Incorrect |
406 ms |
14120 KB |
Output isn't correct |
4 |
Incorrect |
2 ms |
2816 KB |
Output isn't correct |
5 |
Incorrect |
3 ms |
2816 KB |
Output isn't correct |
6 |
Incorrect |
5 ms |
2944 KB |
Output isn't correct |
7 |
Incorrect |
6 ms |
2944 KB |
Output isn't correct |
8 |
Incorrect |
7 ms |
2944 KB |
Output isn't correct |
9 |
Incorrect |
32 ms |
3456 KB |
Output isn't correct |
10 |
Incorrect |
85 ms |
5504 KB |
Output isn't correct |
11 |
Incorrect |
438 ms |
14064 KB |
Output isn't correct |
12 |
Incorrect |
408 ms |
13988 KB |
Output isn't correct |
13 |
Incorrect |
461 ms |
14064 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
265 ms |
8436 KB |
Output isn't correct |
2 |
Incorrect |
571 ms |
24664 KB |
Output isn't correct |
3 |
Incorrect |
426 ms |
18796 KB |
Output isn't correct |
4 |
Incorrect |
308 ms |
9984 KB |
Output isn't correct |
5 |
Incorrect |
306 ms |
9716 KB |
Output isn't correct |
6 |
Incorrect |
305 ms |
9764 KB |
Output isn't correct |
7 |
Incorrect |
303 ms |
8608 KB |
Output isn't correct |
8 |
Incorrect |
266 ms |
8436 KB |
Output isn't correct |
9 |
Incorrect |
533 ms |
24940 KB |
Output isn't correct |
10 |
Incorrect |
554 ms |
24552 KB |
Output isn't correct |
11 |
Incorrect |
553 ms |
24428 KB |
Output isn't correct |
12 |
Incorrect |
546 ms |
21744 KB |
Output isn't correct |
13 |
Incorrect |
506 ms |
27240 KB |
Output isn't correct |
14 |
Incorrect |
434 ms |
18796 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
274 ms |
13808 KB |
Output is correct |
2 |
Incorrect |
563 ms |
22140 KB |
Output isn't correct |
3 |
Correct |
380 ms |
24808 KB |
Output is correct |
4 |
Incorrect |
356 ms |
20332 KB |
Output isn't correct |
5 |
Incorrect |
360 ms |
19944 KB |
Output isn't correct |
6 |
Incorrect |
352 ms |
20028 KB |
Output isn't correct |
7 |
Incorrect |
354 ms |
18236 KB |
Output isn't correct |
8 |
Correct |
377 ms |
24808 KB |
Output is correct |
9 |
Incorrect |
551 ms |
24936 KB |
Output isn't correct |
10 |
Incorrect |
557 ms |
24584 KB |
Output isn't correct |
11 |
Incorrect |
565 ms |
24496 KB |
Output isn't correct |
12 |
Incorrect |
565 ms |
22380 KB |
Output isn't correct |
13 |
Correct |
613 ms |
30568 KB |
Output is correct |
14 |
Correct |
492 ms |
19052 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
566 ms |
24872 KB |
Output isn't correct |
2 |
Incorrect |
556 ms |
22124 KB |
Output isn't correct |
3 |
Incorrect |
497 ms |
30184 KB |
Output isn't correct |
4 |
Incorrect |
546 ms |
24940 KB |
Output isn't correct |
5 |
Incorrect |
557 ms |
24556 KB |
Output isn't correct |
6 |
Incorrect |
533 ms |
24376 KB |
Output isn't correct |
7 |
Incorrect |
565 ms |
22120 KB |
Output isn't correct |
8 |
Incorrect |
504 ms |
30184 KB |
Output isn't correct |
9 |
Incorrect |
426 ms |
18796 KB |
Output isn't correct |