#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5 + 10;
const int maxn = 1e6;
const ll mod = 998244353;
const int sq = 340;
int mn[N], pr[N][20], pt[N], ind[N];
vector<int> edg[N];
vector<pii> vec[N];
vector<int> order;
bool mark[N];
queue<pii> q1, q2;
int n, q, rot;
void input(){
cin>> n>> q;
for(int i = 0; i < n; i++){
int p; cin>> p;
if(p == 0)
rot = i;
else{
p--;
edg[p].push_back(i);
edg[i].push_back(p);
}
}
}
void dfs(int v, int p){
mn[v] = v;
for(int u: edg[v]){
if(u != p){
pr[u][0] = v;
for(int i = 1; i < 20; i++)
pr[u][i] = pr[pr[u][i - 1]][i - 1];
dfs(u, v);
vec[v].push_back({mn[u], u});
mn[v] = min(mn[v], u);
}
}
}
void dfs_or(int v){
for(auto p: vec[v]){
int u = p.second;
dfs_or(u);
}
order.push_back(v);
ind[v] = order.size() - 1;
}
void add(){
int k; cin>> k;
int v = 0;// cin>> v;
while(k--){
int f1 = (q1.size()? q1.front().first: 1e5 + 10);
int f2 = (q2.size()? q2.front().first: 1e5 + 10);
if(f1 < f2){
v = q1.front().second;
mark[v] = 1;
q1.pop();
}
else{
v = q2.front().second;
mark[v] = 1;
q2.pop();
}
}
cout<< v + 1 <<"\n";
}
pii find_pr(int v){
int cnt = 0;
for(int i = 19; i >= 0; i--){
if(mark[pr[v][i]]){
//cout<< i <<" " << pr[v][i] <<"\n";
v = pr[v][i];
cnt += (1 << i);
}
}
return make_pair(v, cnt);
}
void remove(){
int x; cin>> x;
x--;
pii p = find_pr(x);
cout<< p.second <<"\n";
x = p.first;
vector<pii> tmp;
while(q2.size()){
tmp.push_back(q2.front());
q2.pop();
}
bool flag = 0;
for(int i = 0; i < tmp.size(); i++){
if(!flag && tmp[i].first > ind[x]){
q2.push({ind[x], x});
flag = 1;
}
else{
q2.push(tmp[i]);
}
}
if(!flag)
q2.push({ind[x], x});
mark[x] = 0;
}
void reset(){
vector<pii> tmp;
while(q2.size()){
pii p = q2.front();
while(q1.size() && q1.front().first < p.first){
tmp.push_back(q1.front());
q1.pop();
}
tmp.push_back(q2.front());
q2.pop();
}
while(q1.size()){
tmp.push_back(q1.front());
q1.pop();
}
for(int i = 0; i < tmp.size(); i++)
q1.push(tmp[i]);
}
void read_query(){
for(int i = 0; i < q; i++){
if(i && i % sq == 0)
reset();
int t; cin>> t;
if(t == 1){
add();
}
else{
remove();
}
}
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);
input();
for(int i = 0; i <= n; i++){
for(int j = 0; j < 20; j++)
pr[i][j] = n;
}
dfs(rot, -1);
for(int i = 0; i < n; i++)
sort(vec[i].begin(), vec[i].end());
dfs_or(rot);
for(int i = 0; i < n; i++){
q1.push({i, order[i]});
}
read_query();
return 0;
}
Compilation message
ballmachine.cpp: In function 'void remove()':
ballmachine.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | for(int i = 0; i < tmp.size(); i++){
| ~~^~~~~~~~~~~~
ballmachine.cpp: In function 'void reset()':
ballmachine.cpp:129:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for(int i = 0; i < tmp.size(); i++)
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
29532 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
104 ms |
46988 KB |
Execution killed with signal 6 |
| 3 |
Incorrect |
255 ms |
24488 KB |
Output isn't correct |
| 4 |
Runtime error |
15 ms |
29528 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
14 ms |
29528 KB |
Execution killed with signal 11 |
| 6 |
Incorrect |
3 ms |
15144 KB |
Output isn't correct |
| 7 |
Runtime error |
18 ms |
29788 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
14 ms |
29788 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
16 ms |
30296 KB |
Execution killed with signal 6 |
| 10 |
Runtime error |
29 ms |
31764 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
82 ms |
47568 KB |
Execution killed with signal 6 |
| 12 |
Incorrect |
247 ms |
24408 KB |
Output isn't correct |
| 13 |
Runtime error |
122 ms |
47944 KB |
Execution killed with signal 6 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
21492 KB |
Output is correct |
| 2 |
Runtime error |
217 ms |
71892 KB |
Execution killed with signal 6 |
| 3 |
Incorrect |
396 ms |
31976 KB |
Output isn't correct |
| 4 |
Runtime error |
40 ms |
41552 KB |
Execution killed with signal 6 |
| 5 |
Runtime error |
36 ms |
41484 KB |
Execution killed with signal 6 |
| 6 |
Runtime error |
51 ms |
41704 KB |
Execution killed with signal 6 |
| 7 |
Runtime error |
37 ms |
39492 KB |
Execution killed with signal 6 |
| 8 |
Correct |
69 ms |
21504 KB |
Output is correct |
| 9 |
Runtime error |
147 ms |
73956 KB |
Execution killed with signal 6 |
| 10 |
Runtime error |
216 ms |
71704 KB |
Execution killed with signal 6 |
| 11 |
Runtime error |
225 ms |
73264 KB |
Execution killed with signal 6 |
| 12 |
Runtime error |
189 ms |
67020 KB |
Execution killed with signal 6 |
| 13 |
Correct |
351 ms |
39784 KB |
Output is correct |
| 14 |
Incorrect |
408 ms |
31900 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
25300 KB |
Output is correct |
| 2 |
Incorrect |
139 ms |
32972 KB |
Output isn't correct |
| 3 |
Correct |
120 ms |
36344 KB |
Output is correct |
| 4 |
Incorrect |
114 ms |
31588 KB |
Output isn't correct |
| 5 |
Incorrect |
104 ms |
31096 KB |
Output isn't correct |
| 6 |
Incorrect |
104 ms |
31180 KB |
Output isn't correct |
| 7 |
Incorrect |
105 ms |
28940 KB |
Output isn't correct |
| 8 |
Correct |
101 ms |
36464 KB |
Output is correct |
| 9 |
Incorrect |
119 ms |
36148 KB |
Output isn't correct |
| 10 |
Incorrect |
173 ms |
35640 KB |
Output isn't correct |
| 11 |
Incorrect |
125 ms |
35784 KB |
Output isn't correct |
| 12 |
Incorrect |
143 ms |
33180 KB |
Output isn't correct |
| 13 |
Correct |
106 ms |
42440 KB |
Output is correct |
| 14 |
Correct |
107 ms |
29768 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
198 ms |
73420 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
170 ms |
66656 KB |
Execution killed with signal 6 |
| 3 |
Correct |
434 ms |
44112 KB |
Output is correct |
| 4 |
Runtime error |
212 ms |
73432 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
216 ms |
72664 KB |
Execution killed with signal 6 |
| 6 |
Incorrect |
277 ms |
37236 KB |
Output isn't correct |
| 7 |
Runtime error |
177 ms |
66724 KB |
Execution killed with signal 6 |
| 8 |
Correct |
385 ms |
44192 KB |
Output is correct |
| 9 |
Incorrect |
380 ms |
31808 KB |
Output isn't correct |
