#include <bits/stdc++.h>
#define rep(i, a, b) for(int i=(a) ; i<=(b) ; ++i)
#define mp make_pair
#define pii pair<int, int>
#define PB push_back
#define F first
#define S second
#define Task " 12 toan 2 "
using namespace std;
const int N=100005;
int n, Q, root, par[N][20], mn[N], h[N], flag[N];
vector <int > g[N];
int cnt, b[N], dd[N];
priority_queue <int > q;
void setup() {
cin >> n >> Q;
rep(i, 1, n) {
int u; cin >> u;
if(u==0) root=i;
else g[u].PB(i);
}
}
void DFS(int u) {
mn[u]=u;
for(int v:g[u]) {
par[v][0]=u;
rep(i, 1, 16) par[v][i]=par[par[v][i-1]][i-1];
h[v]=h[u]+1;
DFS(v);
mn[u]=min(mn[u], mn[v]);
}
}
bool cmp(int u, int v) {
return mn[u]<mn[v];
}
void xuli(int u) {
sort(g[u].begin(), g[u].end(), cmp);
for(int v:g[u]) xuli(v);
b[++cnt]=u; flag[u]=cnt;
q.push(-cnt);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//freopen(Task".inp", "r", stdin);
//freopen(Task".out", "w", stdout);
setup();
DFS(root);
xuli(root);
while(Q--) {
int t, k;
cin >> t >> k;
if(t==1) {
int id;
while(k--) {
id=-q.top(); q.pop();
dd[b[id]]=1;
}
cout << b[id] << '\n';
} else {
int x=k;
for(int i=17 ; i>=0 ; --i) {
if(dd[par[x][i]]) {
x=par[x][i];
}
}
cout << h[k]-h[x] << '\n';
dd[x]=0;
q.push(-flag[x]);
}
}
return 0;
}
Compilation message
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:59:17: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
int id;
^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
2808 KB |
Output is correct |
2 |
Correct |
117 ms |
11892 KB |
Output is correct |
3 |
Correct |
64 ms |
11640 KB |
Output is correct |
4 |
Correct |
4 ms |
2680 KB |
Output is correct |
5 |
Correct |
4 ms |
2808 KB |
Output is correct |
6 |
Correct |
4 ms |
2904 KB |
Output is correct |
7 |
Correct |
4 ms |
2808 KB |
Output is correct |
8 |
Correct |
5 ms |
2808 KB |
Output is correct |
9 |
Correct |
9 ms |
3320 KB |
Output is correct |
10 |
Correct |
19 ms |
4984 KB |
Output is correct |
11 |
Correct |
104 ms |
11892 KB |
Output is correct |
12 |
Correct |
65 ms |
11608 KB |
Output is correct |
13 |
Correct |
109 ms |
11832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
7840 KB |
Output is correct |
2 |
Correct |
194 ms |
21152 KB |
Output is correct |
3 |
Correct |
82 ms |
15216 KB |
Output is correct |
4 |
Correct |
62 ms |
8908 KB |
Output is correct |
5 |
Correct |
73 ms |
8824 KB |
Output is correct |
6 |
Correct |
59 ms |
8952 KB |
Output is correct |
7 |
Correct |
68 ms |
7672 KB |
Output is correct |
8 |
Correct |
35 ms |
7800 KB |
Output is correct |
9 |
Correct |
162 ms |
21620 KB |
Output is correct |
10 |
Correct |
214 ms |
21236 KB |
Output is correct |
11 |
Correct |
166 ms |
21104 KB |
Output is correct |
12 |
Correct |
165 ms |
18540 KB |
Output is correct |
13 |
Correct |
110 ms |
24052 KB |
Output is correct |
14 |
Correct |
81 ms |
15240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
12324 KB |
Output is correct |
2 |
Correct |
183 ms |
19028 KB |
Output is correct |
3 |
Correct |
155 ms |
22276 KB |
Output is correct |
4 |
Correct |
113 ms |
17748 KB |
Output is correct |
5 |
Correct |
131 ms |
17396 KB |
Output is correct |
6 |
Correct |
133 ms |
17496 KB |
Output is correct |
7 |
Correct |
120 ms |
15604 KB |
Output is correct |
8 |
Correct |
131 ms |
22260 KB |
Output is correct |
9 |
Correct |
184 ms |
21752 KB |
Output is correct |
10 |
Correct |
194 ms |
21364 KB |
Output is correct |
11 |
Correct |
171 ms |
21528 KB |
Output is correct |
12 |
Correct |
190 ms |
19008 KB |
Output is correct |
13 |
Correct |
235 ms |
27504 KB |
Output is correct |
14 |
Correct |
130 ms |
16084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
211 ms |
21976 KB |
Output is correct |
2 |
Correct |
189 ms |
19056 KB |
Output is correct |
3 |
Correct |
145 ms |
26736 KB |
Output is correct |
4 |
Correct |
199 ms |
22032 KB |
Output is correct |
5 |
Correct |
191 ms |
21352 KB |
Output is correct |
6 |
Correct |
156 ms |
21336 KB |
Output is correct |
7 |
Correct |
186 ms |
19156 KB |
Output is correct |
8 |
Correct |
133 ms |
26860 KB |
Output is correct |
9 |
Correct |
88 ms |
15344 KB |
Output is correct |