Submission #159673

#	Time	Username	Problem	Language	Result	Execution time	Memory
159673		Rouge_Hugo	Ball Machine (BOI13_ballmachine)	C++14	16.11 / 100	712 ms	29944 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;
multiset <pair<int,int>>s;
const int N=1e5+10;
vector<int>v[N];
int n,q,lev[N],t[N],pa[N][25],yes[N];
void dfs (int x,int p)
{
    pa[x][0]=p;
    lev[x]=lev[p]+1;
    for(int i=1;i<22;i++)
    {
        pa[x][i]=pa[pa[x][i-1]][i-1];
    }
    for(auto it:v[x])
    {
        if (it!=p)dfs(it,x);
    }
    t[x]=s.size();
    s.insert({t[x],x});
}
void add (int x)
{
    int last;

    while (x--)
    {
       auto l=s.begin();
         last=(*l).second;
        yes[last]=1;
        s.erase(s.begin());
    }
    cout<<last<<endl;
}
void del(int x)
{
    int xx=x;
    for(int i=22;i>-1;i--)
    {
        if (yes[pa[xx][i]]==1)
            xx=pa[xx][i];
    }
    cout<<lev[x]-lev[xx]<<endl;
yes[xx]=0;
s.insert({t[xx],xx});
}
int main()
{
    int x;
    int root =0;
    cin>>n>>q;
    for(int i=1;i<n+1;i++)
    {
        cin>>x;
        if (x==0)
        {
            root=i;
            continue;
        }
        v[x].push_back(i);
    }
    for(int i=1;i<n;i++)
        sort(v[i].begin(),v[i].end());
    dfs (root,0);
    while (q--)
    {
        cin>>x;
        if (x==1)
        {
            cin>>x;
            add(x);

        }
        else {
            cin>>x;
            del(x);
        }
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'void add(int)':
ballmachine.cpp:34:11: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout<<last<<endl;
           ^~~~

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