Submission #666897

#	Time	Username	Problem	Language	Result	Execution time	Memory
666897		mmk	Ball Machine (BOI13_ballmachine)	C++14	0 / 100	1098 ms	15572 KiB

ballmachine

#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);
        }
    }
}

Compilation message (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 | }
      | ^

• Subtask 1: 0 / 25
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40
• Subtask 4: 0 / 5