#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;
que.push(mp(order[pp], pp));
//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 |
536 ms |
12968 KB |
Output isn't correct |
3 |
Incorrect |
408 ms |
13268 KB |
Output isn't correct |
4 |
Incorrect |
2 ms |
2816 KB |
Output isn't correct |
5 |
Incorrect |
3 ms |
2944 KB |
Output isn't correct |
6 |
Incorrect |
5 ms |
2944 KB |
Output isn't correct |
7 |
Incorrect |
7 ms |
2944 KB |
Output isn't correct |
8 |
Incorrect |
7 ms |
2944 KB |
Output isn't correct |
9 |
Incorrect |
35 ms |
3456 KB |
Output isn't correct |
10 |
Incorrect |
98 ms |
5496 KB |
Output isn't correct |
11 |
Incorrect |
533 ms |
12912 KB |
Output isn't correct |
12 |
Incorrect |
409 ms |
13168 KB |
Output isn't correct |
13 |
Incorrect |
525 ms |
12908 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
282 ms |
8128 KB |
Output is correct |
2 |
Incorrect |
637 ms |
23148 KB |
Output isn't correct |
3 |
Incorrect |
426 ms |
18028 KB |
Output isn't correct |
4 |
Incorrect |
356 ms |
9332 KB |
Output isn't correct |
5 |
Incorrect |
352 ms |
9204 KB |
Output isn't correct |
6 |
Incorrect |
349 ms |
9216 KB |
Output isn't correct |
7 |
Incorrect |
351 ms |
8052 KB |
Output isn't correct |
8 |
Correct |
273 ms |
8052 KB |
Output is correct |
9 |
Incorrect |
609 ms |
23784 KB |
Output isn't correct |
10 |
Incorrect |
629 ms |
23156 KB |
Output isn't correct |
11 |
Incorrect |
669 ms |
23148 KB |
Output isn't correct |
12 |
Incorrect |
634 ms |
20456 KB |
Output isn't correct |
13 |
Correct |
473 ms |
26216 KB |
Output is correct |
14 |
Incorrect |
457 ms |
18240 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
298 ms |
13424 KB |
Output is correct |
2 |
Incorrect |
672 ms |
21100 KB |
Output isn't correct |
3 |
Correct |
431 ms |
24104 KB |
Output is correct |
4 |
Incorrect |
412 ms |
19560 KB |
Output isn't correct |
5 |
Incorrect |
407 ms |
19176 KB |
Output isn't correct |
6 |
Incorrect |
414 ms |
19308 KB |
Output isn't correct |
7 |
Incorrect |
398 ms |
17260 KB |
Output isn't correct |
8 |
Correct |
447 ms |
24040 KB |
Output is correct |
9 |
Incorrect |
650 ms |
23788 KB |
Output isn't correct |
10 |
Incorrect |
650 ms |
23404 KB |
Output isn't correct |
11 |
Incorrect |
707 ms |
23276 KB |
Output isn't correct |
12 |
Incorrect |
694 ms |
20972 KB |
Output isn't correct |
13 |
Correct |
748 ms |
29368 KB |
Output is correct |
14 |
Correct |
609 ms |
17772 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
678 ms |
23732 KB |
Output isn't correct |
2 |
Incorrect |
650 ms |
20968 KB |
Output isn't correct |
3 |
Correct |
527 ms |
29164 KB |
Output is correct |
4 |
Incorrect |
643 ms |
23660 KB |
Output isn't correct |
5 |
Incorrect |
641 ms |
23220 KB |
Output isn't correct |
6 |
Incorrect |
612 ms |
23300 KB |
Output isn't correct |
7 |
Incorrect |
681 ms |
20900 KB |
Output isn't correct |
8 |
Correct |
502 ms |
29252 KB |
Output is correct |
9 |
Incorrect |
445 ms |
17960 KB |
Output isn't correct |