#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3+10;
int n,raiz;
int pai[MAXN],cap[MAXN],menor[MAXN];
vector<int> filhos[MAXN];
void build(int v)
{
if(filhos[v].size() == 0)
{
cap[v] = 1;
menor[v] = v;
return;
}
build(filhos[v][0]);
build(filhos[v][1]);
menor[v] = min(menor[filhos[v][0]],menor[filhos[v][1]]);
menor[v] = min(v,menor[v]);
cap[v] = cap[filhos[v][0]] + cap[filhos[v][1]]+1;
}
void update1(int id)
{
cap[id] = 0;
if(filhos[id].size() == 0) return;
update1(filhos[id][0]);
update1(filhos[id][1]);
}
int query1(int id,int k)
{
//cerr << cap[id] << " " << id << "\n";
if(cap[id] == k)
{
update1(id);
return id;
}
cap[id] -= k;
int f1,f2;
f1 = filhos[id][0];
f2 = filhos[id][1];
if(menor[f1] < menor[f2])
{
if(cap[f1] == k)
{
update1(f1);
return f1;
}
if(cap[f1] > k)
{
return query1(f1,k);
}
else
{
int aux = cap[f1];
update1(f1);
return query1(f2,k-cap[f1]);
}
}
else if(menor[f1] > menor[f2])
{
if(cap[f2] == k)
{
update1(f2);
return f2;
}
if(cap[f2] > k)
{
cap[f2] -= k;
return query1(f2,k);
}
else
{
int aux = cap[f2];
update1(f2);
return query1(f1,k-cap[f2]);
}
}
}
int query2(int id,int cont)
{
//cerr << id << " " << cont << "\n";
cap[id]++;
if(pai[id] == id) return cont;
if(cap[pai[id]] > 0) return cont;
return query2(pai[id],cont+1);
}
void update2(int id)
{
cap[id]++;
if(pai[id] == id) return;
update2(pai[id]);
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
int q;
cin >> n >> q;
for(int i = 0; i < n; i++)
{
int aux;
cin >> aux;
if(aux == 0)
{
raiz = i;
pai[i] = i;
}
else
{
pai[i] = aux;
filhos[aux].push_back(i);
}
}
build(raiz);
for(int i = 0; i < q; i++)
{
//cerr << "||" << cap[raiz] << "\n";
int a,b;
cin >> a >> b;
if(a == 1)
cout << query1(raiz,b) << "\n";
else
{
cout << query2(b,0) << "\n";
}
}
}
Compilation message
ballmachine.cpp: In function 'int query1(int, int)':
ballmachine.cpp:53:17: warning: unused variable 'aux' [-Wunused-variable]
53 | int aux = cap[f1];
| ^~~
ballmachine.cpp:72:17: warning: unused variable 'aux' [-Wunused-variable]
72 | int aux = cap[f2];
| ^~~
ballmachine.cpp:77:1: warning: control reaches end of non-void function [-Wreturn-type]
77 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 6 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 7 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
| 12 |
Runtime error |
1 ms |
548 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
1 ms |
456 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
1 ms |
476 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 12 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 10 |
Runtime error |
1 ms |
476 KB |
Execution killed with signal 11 |
| 11 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 11 |
| 12 |
Runtime error |
1 ms |
476 KB |
Execution killed with signal 11 |
| 13 |
Runtime error |
1 ms |
472 KB |
Execution killed with signal 11 |
| 14 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Runtime error |
1 ms |
472 KB |
Execution killed with signal 11 |
| 3 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 4 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 5 |
Runtime error |
1 ms |
472 KB |
Execution killed with signal 11 |
| 6 |
Runtime error |
2 ms |
472 KB |
Execution killed with signal 11 |
| 7 |
Runtime error |
1 ms |
480 KB |
Execution killed with signal 11 |
| 8 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 9 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
