Submission #200936

#	Time	Username	Problem	Language	Result	Execution time	Memory
200936		Shelby	Ball Machine (BOI13_ballmachine)	C++11	0 / 100	334 ms	28920 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];
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;
}

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

    vis[node]=true;

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

    sort(v[node].begin(),v[node].end());

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

            dfs2(v[node][i]);

            ad+=cnt[ v[node][i] ];
        }
    }
}

int main()
{ int n,q,a,b,i,x,root;
scanf("%d%d",&n,&q);
for(i=1;i<=n;i++)
{
    scanf("%d",&a);

    v[a].push_back(i);

    v[i].push_back(a);

    if(a==0) root=i;

    p[i]=a;
}

dfs1(root);

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

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

dfs2(root);

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

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

        scanf("%d",&k);

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

            it--;

            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=20;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;
    }
}

//for(i=1;i<=n;i++) printf("%d\n",order[i]);
    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 'void dfs2(int)':
ballmachine.cpp:44: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 main()':
ballmachine.cpp:58:13: warning: unused variable 'b' [-Wunused-variable]
 { int n,q,a,b,i,x,root;
             ^
ballmachine.cpp:59: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:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&a);
     ~~~~~^~~~~~~~~
ballmachine.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&x);
     ~~~~~^~~~~~~~~
ballmachine.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&k);
         ~~~~~^~~~~~~~~
ballmachine.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&k);
         ~~~~~^~~~~~~~~
ballmachine.cpp: In function 'int dfs1(int)':
ballmachine.cpp:18:39: warning: iteration 19 invokes undefined behavior [-Waggressive-loop-optimizations]
     for(int i=1;i<=20;i++) up[node][i]=up[ up[node][i-1] ][i-1];
                            ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:18:18: note: within this loop
     for(int i=1;i<=20;i++) up[node][i]=up[ up[node][i-1] ][i-1];
                 ~^~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:82:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
 dfs2(root);
 ~~~~^~~~~~

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