Submission #42657

#	Time	Username	Problem	Language	Result	Execution time	Memory
42657		XmtosX	Ball Machine (BOI13_ballmachine)	C++14	8.57 / 100	496 ms	72768 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
int n,minn[100005],root,sz[100005],q,sprs[100005][30];
vector <int> v[100005];
set <pair<int,int > > s;
bool yes[100005];
void dfs (int x,int p)
{
    sz[x]=1;
    minn[x]=x;
    if (p!=-1)
        sprs[x][0]=p;
    for (int i=1;i<30;i++)
        sprs[x][i]=sprs[sprs[x][i-1]][i-1];
    for (int i=0;i<v[x].size();i++)
    {
        if (v[x][i]!=p)
        {
            dfs(v[x][i],x);
            sz[x]+=sz[v[x][i]];
            minn[x]=min(minn[x],minn[v[x][i]]);
        }
    }
}
int main()
{
    cin >>n>>q;
    for (int i=1;i<=n;i++)
    {
        int a;
        cin >>a;
        if (!a)
            root=i;
        else
        {
            v[a].push_back(i);
            v[i].push_back(a);
        }
    }
    dfs (root,-1);
    for (int i=1;i<=n;i++)
    {
        if (v[i].size()==1&&i!=root)
        {
            s.insert({minn[i],i});
        }
    }
    while (q--)
    {
        int t,k;
        cin >>t>>k;
        if (t==1)
        {
            int x;
            while (k--&&!s.empty())
            {
                x= s.begin()->second;
                s.erase(s.begin());
                yes[x]=true;
                if (x!=root)
                    s.insert({minn[sprs[x][0]],sprs[x][0]});
            }
            cout <<x<<"\n";
        }
        else
        {
            int ans=0;
            for (int i=29;i>=0;i--)
            {
                if (yes[sprs[k][i]])
                {
                    k=sprs[k][i];
                    ans+= (1<<i);
                }
            }
            cout <<ans<<"\n";
            yes[k]=false;
            s.insert({minn[k],k});
            if (sprs[k][0]!=root)
                s.erase({minn[sprs[k][0]],k});
        }
    }
    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'void dfs(int, int)':
ballmachine.cpp:15:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[x].size();i++)
                   ^
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:63:20: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cout <<x<<"\n";
                    ^

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