Submission #201126

#	Time	Username	Problem	Language	Result	Execution time	Memory
201126		Shelby	Ball Machine (BOI13_ballmachine)	C++11	100 / 100	423 ms	32504 KiB

ballmachine

#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;

bool vis[MAXN];
int lv[MAXN],cnt[MAXN],order[MAXN],add[MAXN],col[MAXN],p[MAXN],up[MAXN][20],mn[MAXN];
vector<int> v[MAXN];
set< pair<int,int> > give;

int dfs1(int node)
{
    int sz=1;

    vis[node]=true;

    up[node][0]=p[node];

    for(int i=1;i<20;i++) up[node][i]=up[ up[node][i-1] ][i-1];

    for(int i=0;i<v[node].size();i++)
    {
        if( vis[ v[node][i] ]==false )
        {
            lv[ v[node][i] ]=lv[node]+1;

            sz=sz+dfs1( v[node][i] );
        }
    }
    cnt[node]=sz;

    return sz;
}

int dfsmin(int node)
{
    vis[node]=true;

    int mnn=node;

    for(int i=0;i<v[node].size();i++)
    {
        if( vis[ v[node][i] ]==false ) mnn=min(mnn, dfsmin(v[node][i]) );
    }

    mn[node]=mnn;

    return mnn;
}

void dfs2(int node)
{
    int ad=0;

    vis[node]=true;

    order[node]=add[node]+cnt[node];

    vector< pair<int,int> > t;

    for(int i=0;i<v[node].size();i++)
    {
        if( vis[ v[node][i] ]==false ) t.push_back( {mn[ v[node][i] ] , v[node][i]} );
    }

    sort(t.begin(),t.end());

    for(int i=0;i<t.size();i++)
    {
        if(vis[ t[i].second ]==false)
        {
            add[ t[i].second ]=add[node]+ad;

            dfs2( t[i].second );

            ad+=cnt[ t[i].second ];
        }
    }
}

int main()
{ int n,q,a,b,i,x,root;
scanf("%d%d",&n,&q);

for(i=1;i<=n;i++)
{
    scanf("%d",&a);

    if(a!=0)
    {
        v[a].push_back(i);

        v[i].push_back(a);
    }

    if(a==0) root=i;

    p[i]=a;

    mn[i]=i;
}

dfsmin(root);

for(i=1;i<=n;i++) vis[i]=false;

dfs1(root);

for(i=1;i<=n;i++) vis[i]=false;

dfs2(root);

for(i=1;i<=n;i++) give.insert( {order[i],i} );

while(q--)
{
    scanf("%d",&x);

    if(x==1)
    {
        int k,l;

        scanf("%d",&k);

        while(k--)
        {
            auto it=give.begin();

            pair<int,int> tmp=*it;

            col[ tmp.second ]=1;

            l=tmp.second;

            give.erase( it );
        }

        printf("%d\n",l);
    }

    if(x==2)
    {
        int k;

        scanf("%d",&k);

        int y=k;

        for(int j=19;j>=0;j--)
        {
            if(col[ up[y][j] ]==1) y=up[y][j];
        }

        printf("%d\n",abs(lv[k]-lv[y]));

        give.insert( {order[y],y} );

        col[y]=0;
    }
}
    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int dfs1(int)':
ballmachine.cpp:20:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[node].size();i++)
                 ~^~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int dfsmin(int)':
ballmachine.cpp:40:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[node].size();i++)
                 ~^~~~~~~~~~~~~~~
ballmachine.cpp: In function 'void dfs2(int)':
ballmachine.cpp:60:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v[node].size();i++)
                 ~^~~~~~~~~~~~~~~
ballmachine.cpp:67:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<t.size();i++)
                 ~^~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:81:13: warning: unused variable 'b' [-Wunused-variable]
 { int n,q,a,b,i,x,root;
             ^
ballmachine.cpp:82:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d%d",&n,&q);
 ~~~~~^~~~~~~~~~~~~~
ballmachine.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&a);
     ~~~~~^~~~~~~~~
ballmachine.cpp:116:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&x);
     ~~~~~^~~~~~~~~
ballmachine.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&k);
         ~~~~~^~~~~~~~~
ballmachine.cpp:144:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&k);
         ~~~~~^~~~~~~~~
ballmachine.cpp:110:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
 dfs2(root);
 ~~~~^~~~~~

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