이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+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";
if(pai[id] == id) return cont;
if(cap[pai[id]] > 0) return cont;
cap[id]--;
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";
update2(b);
}
}
}
컴파일 시 표준 에러 (stderr) 메시지
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 |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |