oj.uz

Submission #201126

# Submission time Handle Problem Language Result Execution time Memory
201126 2020-02-09T11:51:30 Z Shelby Ball Machine (BOI13_ballmachine) C++11
100 / 100
 423 ms 32504 KB 
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2808 KB Output is correct
2 Correct 214 ms 16376 KB Output is correct
3 Correct 137 ms 15992 KB Output is correct
4 Correct 6 ms 2680 KB Output is correct
5 Correct 7 ms 2712 KB Output is correct
6 Correct 7 ms 2936 KB Output is correct
7 Correct 8 ms 2936 KB Output is correct
8 Correct 8 ms 2936 KB Output is correct
9 Correct 16 ms 3580 KB Output is correct
10 Correct 40 ms 6008 KB Output is correct
11 Correct 218 ms 16120 KB Output is correct
12 Correct 147 ms 16124 KB Output is correct
13 Correct 178 ms 16120 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 8568 KB Output is correct
2 Correct 355 ms 27616 KB Output is correct
3 Correct 162 ms 22120 KB Output is correct
4 Correct 119 ms 10564 KB Output is correct
5 Correct 123 ms 10616 KB Output is correct
6 Correct 114 ms 10616 KB Output is correct
7 Correct 110 ms 9336 KB Output is correct
8 Correct 66 ms 8568 KB Output is correct
9 Correct 300 ms 27512 KB Output is correct
10 Correct 331 ms 27512 KB Output is correct
11 Correct 297 ms 27640 KB Output is correct
12 Correct 329 ms 24696 KB Output is correct
13 Correct 247 ms 28508 KB Output is correct
14 Correct 178 ms 22092 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 15240 KB Output is correct
2 Correct 360 ms 25252 KB Output is correct
3 Correct 243 ms 26360 KB Output is correct
4 Correct 269 ms 22480 KB Output is correct
5 Correct 277 ms 22520 KB Output is correct
6 Correct 277 ms 22520 KB Output is correct
7 Correct 300 ms 20600 KB Output is correct
8 Correct 320 ms 26240 KB Output is correct
9 Correct 401 ms 27640 KB Output is correct
10 Correct 417 ms 27840 KB Output is correct
11 Correct 383 ms 27704 KB Output is correct
12 Correct 423 ms 25264 KB Output is correct
13 Correct 393 ms 32504 KB Output is correct
14 Correct 279 ms 22892 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 27768 KB Output is correct
2 Correct 414 ms 25244 KB Output is correct
3 Correct 284 ms 31712 KB Output is correct
4 Correct 394 ms 27808 KB Output is correct
5 Correct 374 ms 27768 KB Output is correct
6 Correct 339 ms 27768 KB Output is correct
7 Correct 423 ms 25352 KB Output is correct
8 Correct 265 ms 31736 KB Output is correct
9 Correct 161 ms 22116 KB Output is correct