#pragma GCC optimization O2
#pragma GCC optimization "unroll-loop"
#pragma target ("avx2")
#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e5 + 9;
const ll Log2 = 20;
const ll inf = 1e18 + 7;
priority_queue<LL,vector<LL>,greater<LL>> pq[N];
vector<ll> g[N];
ll n,Q,root,x,mn[N],par[N][Log2],d[N],last,type,take[N];
void DFS(ll u){
for (ll i = 1;i < Log2;i++) if ((1 << i) <= d[u])
par[u][i] = par[par[u][i - 1]][i - 1];
mn[u] = u;
for (auto i : g[u]){
par[i][0] = u; d[i] = d[u] + 1; DFS(i);
mn[u] = min(mn[u],mn[i]); pq[u].push({mn[i],i});
}
}
void Add(ll u){
if (pq[u].empty()){
take[u] = 1; last = u; return;
}
LL t = pq[u].top(); Add(t.sc);
}
ll Jump(ll node,ll step){
//cout<<par[node][0]; exit(0);
for (ll i = Log2 - 1;i >= 0;i--){
if (step >= (1 << i)){
node = par[node][i]; step -= (1 << i);
}
}
return node;
}
int main(){
ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
#define task "test"
if (fopen(task".INP","r")){
freopen(task".INP","r",stdin);
//freopen(task".OUT","w",stdout);
}
cin>>n>>Q;
for (ll i = 1;i <= n;i++){
cin>>x;
if (x == 0) root = i;
else g[x].push_back(i);
}
DFS(root); last = root;
//cout<<Jump(8,2); return 0;
while(Q--){
cin>>type>>x;
if (type == 1){
last = 1;
while(x--){
if (last != root){
last = par[last][0]; pq[last].pop();
}
//cout<<last; return 0;
Add(last);
}
cout<<last<<"\n";
//cout<<take[5]; return 0;
}
else{
ll l,m,h; l = 0; h = d[x];
while(l <= h){
m = (l + h)/2; ll nxt = Jump(x,m);
if (!take[nxt]) h = m - 1;
else l = m + 1;
}
ll cur = Jump(x,h);
cout<<h<<"\n";
take[cur] = 0; //cout<<x<<" "<<h<<"\n";
if (cur != root){
ll p = par[cur][0]; pq[p].push({mn[cur],cur});
//cout<<p<<" "<<cur<<"\n";
}
}
}
}
Compilation message
ballmachine.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
1 | #pragma GCC optimization O2
|
ballmachine.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
2 | #pragma GCC optimization "unroll-loop"
|
ballmachine.cpp:3: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
3 | #pragma target ("avx2")
|
ballmachine.cpp:14:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
14 | const ll inf = 1e18 + 7;
| ~~~~~^~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | freopen(task".INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
5836 KB |
Output isn't correct |
| 2 |
Incorrect |
145 ms |
14436 KB |
Output isn't correct |
| 3 |
Incorrect |
73 ms |
14440 KB |
Output isn't correct |
| 4 |
Runtime error |
10 ms |
11612 KB |
Execution killed with signal 6 |
| 5 |
Incorrect |
4 ms |
5836 KB |
Output isn't correct |
| 6 |
Incorrect |
4 ms |
5836 KB |
Output isn't correct |
| 7 |
Incorrect |
5 ms |
5964 KB |
Output isn't correct |
| 8 |
Incorrect |
4 ms |
5936 KB |
Output isn't correct |
| 9 |
Incorrect |
10 ms |
6220 KB |
Output isn't correct |
| 10 |
Incorrect |
21 ms |
7828 KB |
Output isn't correct |
| 11 |
Runtime error |
141 ms |
28612 KB |
Execution killed with signal 6 |
| 12 |
Incorrect |
72 ms |
14464 KB |
Output isn't correct |
| 13 |
Runtime error |
110 ms |
30300 KB |
Execution killed with signal 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1088 ms |
10548 KB |
Time limit exceeded |
| 2 |
Incorrect |
365 ms |
24956 KB |
Output isn't correct |
| 3 |
Incorrect |
77 ms |
17692 KB |
Output isn't correct |
| 4 |
Incorrect |
102 ms |
11752 KB |
Output isn't correct |
| 5 |
Incorrect |
135 ms |
11484 KB |
Output isn't correct |
| 6 |
Runtime error |
143 ms |
24840 KB |
Execution killed with signal 11 |
| 7 |
Incorrect |
116 ms |
10308 KB |
Output isn't correct |
| 8 |
Execution timed out |
1078 ms |
10772 KB |
Time limit exceeded |
| 9 |
Incorrect |
285 ms |
25372 KB |
Output isn't correct |
| 10 |
Incorrect |
348 ms |
24836 KB |
Output isn't correct |
| 11 |
Incorrect |
307 ms |
25848 KB |
Output isn't correct |
| 12 |
Incorrect |
306 ms |
21316 KB |
Output isn't correct |
| 13 |
Execution timed out |
1075 ms |
28748 KB |
Time limit exceeded |
| 14 |
Incorrect |
78 ms |
17724 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
107 ms |
15816 KB |
Output isn't correct |
| 2 |
Incorrect |
402 ms |
22444 KB |
Output isn't correct |
| 3 |
Incorrect |
268 ms |
27292 KB |
Output isn't correct |
| 4 |
Incorrect |
195 ms |
21520 KB |
Output isn't correct |
| 5 |
Incorrect |
258 ms |
20748 KB |
Output isn't correct |
| 6 |
Incorrect |
251 ms |
20932 KB |
Output isn't correct |
| 7 |
Incorrect |
275 ms |
19020 KB |
Output isn't correct |
| 8 |
Incorrect |
278 ms |
27124 KB |
Output isn't correct |
| 9 |
Incorrect |
313 ms |
25556 KB |
Output isn't correct |
| 10 |
Incorrect |
435 ms |
24604 KB |
Output isn't correct |
| 11 |
Incorrect |
492 ms |
24924 KB |
Output isn't correct |
| 12 |
Incorrect |
369 ms |
22336 KB |
Output isn't correct |
| 13 |
Incorrect |
483 ms |
32876 KB |
Output isn't correct |
| 14 |
Incorrect |
128 ms |
17852 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
361 ms |
25504 KB |
Output isn't correct |
| 2 |
Incorrect |
378 ms |
22724 KB |
Output isn't correct |
| 3 |
Execution timed out |
1091 ms |
31812 KB |
Time limit exceeded |
| 4 |
Incorrect |
364 ms |
25540 KB |
Output isn't correct |
| 5 |
Incorrect |
402 ms |
24664 KB |
Output isn't correct |
| 6 |
Incorrect |
499 ms |
24772 KB |
Output isn't correct |
| 7 |
Incorrect |
379 ms |
22784 KB |
Output isn't correct |
| 8 |
Execution timed out |
1098 ms |
31628 KB |
Time limit exceeded |
| 9 |
Runtime error |
91 ms |
34016 KB |
Execution killed with signal 6 |
