#include <bits/stdc++.h>
using namespace std;
const int N = 100*1000+5;
int par[N];
vector<int> g[N];
int depth[N];
int d[N][25];
int sub[N];
void dfs(int v,int p = 0){
depth[v] = depth[p]+1;
d[v][0] = par[v];
sub[v] = v;
for(int i = 0;i<g[v].size();i++){
int to = g[v][i];
if(to == p) continue;
dfs(to,v);
sub[v] = min(sub[v],sub[to]);
}
}
pair<int,int> lca(int u,int v){
bool f = false;
if(depth[u]>depth[v]){
swap(u,v);
f = true;
}
int dif = depth[v]-depth[u];
for(int i = 0;i<=20;i++){
if((dif>>i)&1) v = d[v][i];
}
// cout<<u<< " "<<v<<endl;
for(int i = 20;i>=0;i--){
if(d[u][i] == d[v][i]) continue;
u = d[u][i];
v = d[v][i];
}
if(f) swap(u,v);
return {u,v};
}
bool cmp(int u,int v){
pair<int,int> x = lca(u,v);
if(x.first == x.second) return depth[u]>depth[v];
return sub[x.first]<sub[x.second];
}
int hrt[N];
bool used[N];
int main(){
ios_base::sync_with_stdio(false);
int n,q;
cin>>n>>q;
for(int i = 1;i<=n;i++){
int x;
cin>>x;
if(!x) x = -1;
par[i] = x;
g[i].push_back(x);
g[x].push_back(i);
}
memset(d,-1,sizeof(d));
dfs(1);
for(int k = 1;k<=20;k++){
for(int i = 1;i<=n;i++){
if(d[i][k-1]!=-1){
d[i][k] = d[d[i][k-1]][k-1];
}
}
}
vector<int> all;
for(int i = 1;i<=n;i++) all.push_back(i);
sort(all.begin(),all.end(),cmp);
//for(int i = 0;i<all.size();i++) cout<<all[i]<<" ";
//cout<<endl;
set<pair<int,int> > ms;
for(int i = 0;i<all.size();i++){
ms.insert({i,all[i]});
hrt[all[i]] = i;
}
/*int x,y;
while(cin>>x>>y){
pair<int,int> w = lca(x,y);
cout<<w.first<<" "<<w.second<<endl;
}*/
while(q--){
int tp;
cin>>tp;
if(tp == 1){
int k;
cin>>k;
while(k--){
pair<int,int> x = *(ms.begin());
ms.erase(ms.begin());
used[x.second] = 1;
if(!k){
cout<<x.second<<endl;
}
}
}
else{
int x;
cin>>x;
int ans = 0;
while(used[x]){
int pr = par[x];
if(pr == -1 || !used[pr]){
ms.insert({hrt[x],x});
used[x] = 0;
break;
}
ans++;
x = par[x];
}
cout<<ans<<endl;
}
}
return 0;
}
Compilation message
ballmachine.cpp: In function 'void dfs(int, int)':
ballmachine.cpp:13:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<g[v].size();i++){
~^~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<all.size();i++){
~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
13 ms |
12536 KB |
Output isn't correct |
| 2 |
Incorrect |
644 ms |
20592 KB |
Output isn't correct |
| 3 |
Correct |
588 ms |
20512 KB |
Output is correct |
| 4 |
Correct |
13 ms |
12536 KB |
Output is correct |
| 5 |
Incorrect |
13 ms |
12536 KB |
Output isn't correct |
| 6 |
Incorrect |
17 ms |
12664 KB |
Output isn't correct |
| 7 |
Execution timed out |
1061 ms |
12536 KB |
Time limit exceeded |
| 8 |
Incorrect |
19 ms |
12536 KB |
Output isn't correct |
| 9 |
Incorrect |
49 ms |
12920 KB |
Output isn't correct |
| 10 |
Execution timed out |
1069 ms |
14428 KB |
Time limit exceeded |
| 11 |
Incorrect |
690 ms |
20524 KB |
Output isn't correct |
| 12 |
Correct |
620 ms |
20340 KB |
Output is correct |
| 13 |
Incorrect |
606 ms |
20328 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
315 ms |
16132 KB |
Output isn't correct |
| 2 |
Execution timed out |
1056 ms |
25864 KB |
Time limit exceeded |
| 3 |
Incorrect |
755 ms |
23944 KB |
Output isn't correct |
| 4 |
Incorrect |
440 ms |
17468 KB |
Output isn't correct |
| 5 |
Execution timed out |
1074 ms |
16712 KB |
Time limit exceeded |
| 6 |
Incorrect |
866 ms |
17400 KB |
Output isn't correct |
| 7 |
Execution timed out |
1081 ms |
16896 KB |
Time limit exceeded |
| 8 |
Incorrect |
314 ms |
16248 KB |
Output isn't correct |
| 9 |
Incorrect |
868 ms |
27124 KB |
Output isn't correct |
| 10 |
Execution timed out |
1085 ms |
26228 KB |
Time limit exceeded |
| 11 |
Incorrect |
998 ms |
26140 KB |
Output isn't correct |
| 12 |
Execution timed out |
1073 ms |
26348 KB |
Time limit exceeded |
| 13 |
Incorrect |
932 ms |
26868 KB |
Output isn't correct |
| 14 |
Incorrect |
745 ms |
24048 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1088 ms |
19516 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1089 ms |
25328 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1092 ms |
24820 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1078 ms |
23792 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1071 ms |
23236 KB |
Time limit exceeded |
| 6 |
Execution timed out |
1081 ms |
23692 KB |
Time limit exceeded |
| 7 |
Execution timed out |
1083 ms |
22900 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1078 ms |
24944 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1086 ms |
26356 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1083 ms |
25184 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1088 ms |
25852 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1085 ms |
25332 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1085 ms |
28400 KB |
Time limit exceeded |
| 14 |
Correct |
841 ms |
24176 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1081 ms |
26612 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1073 ms |
25076 KB |
Time limit exceeded |
| 3 |
Incorrect |
980 ms |
28656 KB |
Output isn't correct |
| 4 |
Execution timed out |
1070 ms |
26484 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1082 ms |
25716 KB |
Time limit exceeded |
| 6 |
Incorrect |
990 ms |
26384 KB |
Output isn't correct |
| 7 |
Execution timed out |
1086 ms |
25204 KB |
Time limit exceeded |
| 8 |
Incorrect |
949 ms |
28596 KB |
Output isn't correct |
| 9 |
Incorrect |
743 ms |
24044 KB |
Output isn't correct |
