#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 1e5 + 10, MAXLOG = 22;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
int n, que;
int p[MAXN], root;
vector < int > g[MAXN];
void read()
{
cin >> n >> que;
for (int i = 1; i <= n; ++ i)
{
cin >> p[i];
if(!p[i])root = i;
else g[p[i]].push_back(i);
}
}
int points[MAXN], lvl[MAXN], cnt;
int sub[MAXN];
void dfs00(int beg, int h)
{
sub[beg] = beg;
lvl[beg] = h;
int nb;
for (int i = 0; i < g[beg].size(); ++ i)
{
nb = g[beg][i];
dfs00(nb, h+1);
sub[beg] = min(sub[beg], sub[nb]);
}
}
bool cmp(int a, int b)
{
return (sub[a] < sub[b]);
}
void sort_g()
{
for (int i = 1; i <= n; ++ i)
sort(g[i].begin(), g[i].end(), cmp);
}
void dfs0(int beg)
{
int nb;
for (int i = 0; i < g[beg].size(); ++ i)
{
nb = g[beg][i];
dfs0(nb);
}
cnt ++;
points[beg] = cnt;
}
int used[MAXN];
priority_queue < pair < int, int > > q;
int query_type1(int x)
{
int v = 0;
while(x --)
{
v = q.top().second;
//cout << v << endl;
used[v] = 1;
q.pop();
}
return v;
}
int jump[MAXN][MAXLOG];
void make_jumps()
{
for (int i = 1; i <= n; ++ i)
jump[i][0] = p[i];
for (int j = 1; j <= 17; ++ j)
for (int i = 1; i <= n; ++ i)
jump[i][j] = jump[jump[i][j-1]][j-1];
}
int find_ans(int x)
{
int newx = x;
for (int j = 17; j >= 0; -- j)
{
int p = jump[x][j];
if(p == 0)continue;
if(used[p] == 1)x = p;
}
return x;
}
int main()
{
speed();
read();
dfs00(root, 1);
sort_g();
dfs0(root);
for (int i = 1; i <= n; ++ i)
q.push(make_pair(-points[i], i));
make_jumps();
int t, x;
while(que --)
{
cin >> t >> x;
if(t == 1)
cout << query_type1(x) << endl;
else
{
int xx = x;
x = find_ans(x);
q.push(make_pair(-points[x], x));
used[x] = 0;
cout << lvl[xx] - lvl[x] << endl;
}
}
return 0;
}
Compilation message
ballmachine.cpp: In function 'void dfs00(int, int)':
ballmachine.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for (int i = 0; i < g[beg].size(); ++ i)
| ~~^~~~~~~~~~~~~~~
ballmachine.cpp: In function 'void dfs0(int)':
ballmachine.cpp:54:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (int i = 0; i < g[beg].size(); ++ i)
| ~~^~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int find_ans(int)':
ballmachine.cpp:89:9: warning: unused variable 'newx' [-Wunused-variable]
89 | int newx = x;
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4440 KB |
Output is correct |
2 |
Correct |
52 ms |
13008 KB |
Output is correct |
3 |
Correct |
33 ms |
13064 KB |
Output is correct |
4 |
Correct |
1 ms |
4440 KB |
Output is correct |
5 |
Correct |
1 ms |
4440 KB |
Output is correct |
6 |
Correct |
1 ms |
4952 KB |
Output is correct |
7 |
Correct |
1 ms |
4700 KB |
Output is correct |
8 |
Correct |
1 ms |
4700 KB |
Output is correct |
9 |
Correct |
4 ms |
6748 KB |
Output is correct |
10 |
Correct |
11 ms |
7352 KB |
Output is correct |
11 |
Correct |
50 ms |
13000 KB |
Output is correct |
12 |
Correct |
41 ms |
13244 KB |
Output is correct |
13 |
Correct |
48 ms |
13000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
9176 KB |
Output is correct |
2 |
Correct |
81 ms |
19408 KB |
Output is correct |
3 |
Correct |
43 ms |
15840 KB |
Output is correct |
4 |
Correct |
36 ms |
10968 KB |
Output is correct |
5 |
Correct |
42 ms |
10964 KB |
Output is correct |
6 |
Correct |
38 ms |
10964 KB |
Output is correct |
7 |
Correct |
41 ms |
10240 KB |
Output is correct |
8 |
Correct |
23 ms |
9176 KB |
Output is correct |
9 |
Correct |
67 ms |
19856 KB |
Output is correct |
10 |
Correct |
84 ms |
19464 KB |
Output is correct |
11 |
Correct |
67 ms |
19660 KB |
Output is correct |
12 |
Correct |
71 ms |
17860 KB |
Output is correct |
13 |
Correct |
53 ms |
22704 KB |
Output is correct |
14 |
Correct |
41 ms |
15816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
14544 KB |
Output is correct |
2 |
Correct |
75 ms |
18124 KB |
Output is correct |
3 |
Correct |
57 ms |
21712 KB |
Output is correct |
4 |
Correct |
54 ms |
18632 KB |
Output is correct |
5 |
Correct |
67 ms |
18140 KB |
Output is correct |
6 |
Correct |
57 ms |
18244 KB |
Output is correct |
7 |
Correct |
50 ms |
16848 KB |
Output is correct |
8 |
Correct |
56 ms |
21708 KB |
Output is correct |
9 |
Correct |
83 ms |
20032 KB |
Output is correct |
10 |
Correct |
85 ms |
19660 KB |
Output is correct |
11 |
Correct |
79 ms |
19588 KB |
Output is correct |
12 |
Correct |
74 ms |
18140 KB |
Output is correct |
13 |
Correct |
86 ms |
24004 KB |
Output is correct |
14 |
Correct |
63 ms |
15824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
20224 KB |
Output is correct |
2 |
Correct |
82 ms |
18088 KB |
Output is correct |
3 |
Correct |
54 ms |
24004 KB |
Output is correct |
4 |
Correct |
77 ms |
20256 KB |
Output is correct |
5 |
Correct |
78 ms |
19656 KB |
Output is correct |
6 |
Correct |
76 ms |
19780 KB |
Output is correct |
7 |
Correct |
78 ms |
18116 KB |
Output is correct |
8 |
Correct |
54 ms |
24008 KB |
Output is correct |
9 |
Correct |
41 ms |
15880 KB |
Output is correct |