Submission #203208

#	Time	Username	Problem	Language	Result	Execution time	Memory
203208		mdn2002	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	813 ms	37368 KiB

ballmachine

#include<bits/stdc++.h>
using namespace std;
int n,m,rt,st[100500],fn[100500],tim=1,mn[100500],on[100500],spt[100500][30],dp[100500];
vector<int>gr[100500];
set<pair<int,int> >s;
void dfs(int x)
{
    mn[x]=x;
    for(int i=0; i<gr[x].size(); i++)
    {
        int u=gr[x][i];
        dfs(u);
        mn[x]=min(mn[x],mn[u]);
    }
}
void dfs1(int x,int p)
{
    spt[x][0]=p;
    dp[x]=dp[p]+1;
    st[x]=tim++;
    vector<pair<int,int> >v;
    for(int i=0; i<gr[x].size(); i++)
    {
        int u=gr[x][i];
        v.push_back({mn[u],u});
    }
    sort(v.begin(),v.end());
    for(int i=gr[x].size()-1; i>=0; i--)
    {
        int u=v[i].second;
        dfs1(u,x);
    }
    fn[x]=tim;
}
bool ck(int x,int mid)
{
    int dif=mid;
    if(dif>dp[x])return 0;
    for(int i=0; i<=21; i++)
    {
        if((dif&(1<<i)))x=spt[x][i];
    }
    if(on[x]==0)return 0;
    else return 1;
}
int main()
{
    scanf("%d",&n);
    scanf("%d",&m);
    for(int i=1; i<=n; i++)
    {
        int x;
        scanf("%d",&x);
        if(x==0)
        {
            rt=i;
            continue;
        }
        gr[x].push_back(i);
    }
    dfs(rt);
    dfs1(rt,0);
    for(int i=1; i<=n; i++)s.insert({st[i],i});
    for(int i=1; i<=25; i++)
    {
        for(int j=1; j<=n; j++)spt[j][i]=spt[spt[j][i-1]][i-1];
    }
    while(m--)
    {
        int t,x;
        scanf("%d",&t);
        scanf("%d",&x);
        if(t==1)
        {
            int to;
            while(x--)
            {
                pair<int,int>z=*--s.end();
                s.erase(--s.end());
                to=z.second;
                on[to]++;
            }
            printf("%d\n",to);
        }
        else
        {
            int l=0,r=n,mid;
            while(l<r)
            {
                mid=(l+r)/2;
                if(ck(x,mid))l=mid+1;
                else r=mid;
            }
            printf("%d\n",l-1);
            int dif=l-1;
            for(int i=0; i<=21; i++)
            {
                if((dif&(1<<i)))x=spt[x][i];
            }
            on[x]=0;
            s.insert({st[x],x});
        }
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'void dfs(int)':
ballmachine.cpp:9:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<gr[x].size(); i++)
                  ~^~~~~~~~~~~~~
ballmachine.cpp: In function 'void dfs1(int, int)':
ballmachine.cpp:22:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<gr[x].size(); i++)
                  ~^~~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
ballmachine.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&m);
     ~~~~~^~~~~~~~~
ballmachine.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
         ~~~~~^~~~~~~~~
ballmachine.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&t);
         ~~~~~^~~~~~~~~
ballmachine.cpp:72:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x);
         ~~~~~^~~~~~~~~

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