Submission #520955

#	Time	Username	Problem	Language	Result	Execution time	Memory
520955		sicho_mohit	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	503 ms	29656 KiB

ballmachine

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ff first
#define ss second
using namespace std ;
const int N=1e5;
const int M=16;
vector<int>v[N+5];
int dis[N+5], parent[N+5][M+5];
int order[N+5], submin[N+5];
bool is[N+5];
int cnt=0;
bool comp(int a , int b)
{
    return submin[a]<submin[b];
}
void dfs1(int c , int p , int d)
{
    submin[c]=c;
    parent[c][0]=p;
    dis[c]=d;
    for (int i=1;i<=M;i++)
    {
        parent[c][i]=parent[parent[c][i-1]][i-1];
    }
    for (int i=0;i<v[c].size();i++)
    {
        if(v[c][i]!=p)
        {
        dfs1(v[c][i],c,d+1);
        submin[c]=min(submin[c],submin[v[c][i]]);
        }
    }
}
void arrange(int c , int p)
{
    for (int i=0;i<v[c].size();i++)
    {
        if(v[c][i]!=p)
        {
            arrange(v[c][i],c);
        }
    }
    order[c]=cnt++;
}
int findk(int node)
{
    for (int i=M;i>=0;i--)
    {
        if(is[parent[node][i]])
        {
            node=parent[node][i];
        }
    }
    return node;
}
int main ()
{
    int n  , q ;
    cin >> n >> q ;
    int root=1;
    for (int i=1;i<=n;i++)
    {
        int a;
        cin >> a ;
        if(a)
        {
        v[a].pb(i);
        v[i].pb(a);
        }
        else
        root=i;
    }
    dfs1(root,root,1);
    for (int i=1;i<=n;i++)
    sort(v[i].begin(),v[i].end(),comp);
    arrange(root,root);
    set<pair<int,int>>s;
    for (int i=1;i<=n;i++)
    {
        s.insert({order[i],i});
    }
    while(q--)
    {
        int t , k ;
        cin >> t >> k ;
        if(t==1)
        {
            if(k)
            {
            int ans=0;
            while(k--)
            {
                pair<int,int>temp=*(s.begin());
                s.erase(temp);
                is[temp.ss]=true;
                ans=temp.ss;
            }
            cout<<ans<<"\n";
            }
        }
        else
        {
            // find the highest ancestor from k
            int node=findk(k);
            cout<<dis[k]-dis[node]<<"\n";
            is[node]=false;
            s.insert({order[node],node});
        }
    }

}

Compilation message (stderr)

ballmachine.cpp: In function 'void dfs1(int, int, int)':
ballmachine.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int i=0;i<v[c].size();i++)
      |                  ~^~~~~~~~~~~~
ballmachine.cpp: In function 'void arrange(int, int)':
ballmachine.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i=0;i<v[c].size();i++)
      |                  ~^~~~~~~~~~~~

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