#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<int>> al;
vector<int> par;
vector<int> mn;
vector<int> ball;
vector<int> order;
set<pair<int,int>> next_node;
int root,n;
void dfs(int u) {
for (int v: al[u]) {
dfs(v);
}
order[u]=next_node.size()+1;
next_node.insert({order[u],u});
}
void mndfs(int u) {
mn[u]=u;
set<pair<int,int>> o;
for (int v: al[u]) {
mndfs(v);
mn[u]=min(mn[u],mn[v]);
o.insert({mn[v],v});
}
al[u].clear();
for (auto i: o) {
al[u].push_back(i.second);
}
}
int add_ball() {
auto b=*next_node.begin();
next_node.erase(next_node.begin());
ball[b.second]=1;
return b.second;
}
int main() {
int q; cin>>n>>q;
al.assign(n+1,vector<int>());
par.assign(n+1,-1);
mn.assign(n+1,1e9);
ball.assign(n+1,0);
order.assign(n+1,0);
for (int i=1; i<=n; i++) {
int p; cin>>p;
if (p==0) {
root=i;
} else {
al[p].push_back(i);
par[i]=p;
}
}
for (int i=1; i<=n; i++) {
sort(al[i].begin(),al[i].end());
}
mndfs(root);
dfs(root);
while (q--) {
int t; cin>>t;
if (t==1) {
int k; cin>>k;
int ans;
for (int i=0; i<k; i++) {
ans=add_ball();
}
cout<<ans<<"\n";
} else {
int x; cin>>x;
int curr=x;
int ans=0;
while (par[curr]!=-1&&ball[par[curr]]) {
curr=par[curr];
ans++;
}
next_node.insert({order[curr],curr});
ball[curr]=0;
cout<<ans<<"\n";
}
}
return 0;
}
Compilation message
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:71:24: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
71 | cout<<ans<<"\n";
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
240 ms |
7248 KB |
Output is correct |
3 |
Correct |
186 ms |
7412 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
2 ms |
348 KB |
Output is correct |
8 |
Correct |
2 ms |
348 KB |
Output is correct |
9 |
Correct |
14 ms |
864 KB |
Output is correct |
10 |
Correct |
58 ms |
2372 KB |
Output is correct |
11 |
Correct |
247 ms |
7148 KB |
Output is correct |
12 |
Correct |
163 ms |
7408 KB |
Output is correct |
13 |
Correct |
218 ms |
7268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
114 ms |
5468 KB |
Output is correct |
2 |
Correct |
203 ms |
18780 KB |
Output is correct |
3 |
Correct |
192 ms |
10420 KB |
Output is correct |
4 |
Correct |
135 ms |
5976 KB |
Output is correct |
5 |
Correct |
141 ms |
5968 KB |
Output is correct |
6 |
Correct |
133 ms |
5976 KB |
Output is correct |
7 |
Correct |
136 ms |
4444 KB |
Output is correct |
8 |
Correct |
114 ms |
5476 KB |
Output is correct |
9 |
Correct |
198 ms |
19224 KB |
Output is correct |
10 |
Correct |
196 ms |
18768 KB |
Output is correct |
11 |
Correct |
197 ms |
18772 KB |
Output is correct |
12 |
Correct |
205 ms |
14680 KB |
Output is correct |
13 |
Correct |
170 ms |
24916 KB |
Output is correct |
14 |
Correct |
180 ms |
10700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1050 ms |
10104 KB |
Time limit exceeded |
2 |
Execution timed out |
1041 ms |
14904 KB |
Time limit exceeded |
3 |
Execution timed out |
1059 ms |
22284 KB |
Time limit exceeded |
4 |
Execution timed out |
1026 ms |
15740 KB |
Time limit exceeded |
5 |
Execution timed out |
1052 ms |
15188 KB |
Time limit exceeded |
6 |
Execution timed out |
1056 ms |
15408 KB |
Time limit exceeded |
7 |
Execution timed out |
1062 ms |
12284 KB |
Time limit exceeded |
8 |
Execution timed out |
1099 ms |
22612 KB |
Time limit exceeded |
9 |
Execution timed out |
1046 ms |
19416 KB |
Time limit exceeded |
10 |
Execution timed out |
1045 ms |
19028 KB |
Time limit exceeded |
11 |
Execution timed out |
1060 ms |
18820 KB |
Time limit exceeded |
12 |
Execution timed out |
1081 ms |
15172 KB |
Time limit exceeded |
13 |
Execution timed out |
1059 ms |
27820 KB |
Time limit exceeded |
14 |
Correct |
218 ms |
10448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1020 ms |
19124 KB |
Time limit exceeded |
2 |
Execution timed out |
1051 ms |
14876 KB |
Time limit exceeded |
3 |
Correct |
195 ms |
27984 KB |
Output is correct |
4 |
Execution timed out |
1083 ms |
19268 KB |
Time limit exceeded |
5 |
Execution timed out |
1030 ms |
18772 KB |
Time limit exceeded |
6 |
Correct |
323 ms |
19112 KB |
Output is correct |
7 |
Execution timed out |
1074 ms |
14932 KB |
Time limit exceeded |
8 |
Correct |
193 ms |
27984 KB |
Output is correct |
9 |
Correct |
174 ms |
10448 KB |
Output is correct |