oj.uz

Submission #200936

# Submission time Handle Problem Language Result Execution time Memory
200936 2020-02-08T16:54:13 Z Shelby Ball Machine (BOI13_ballmachine) C++11
0 / 100
 334 ms 28920 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];
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

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

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2808 KB Output isn't correct
2 Incorrect 181 ms 15864 KB Output isn't correct
3 Incorrect 126 ms 15712 KB Output isn't correct
4 Runtime error 10 ms 5240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Incorrect 7 ms 2680 KB Output isn't correct
6 Incorrect 7 ms 2936 KB Output isn't correct
7 Runtime error 11 ms 5624 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Incorrect 8 ms 2936 KB Output isn't correct
9 Incorrect 15 ms 3448 KB Output isn't correct
10 Runtime error 42 ms 11512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Incorrect 191 ms 15864 KB Output isn't correct
12 Incorrect 129 ms 15736 KB Output isn't correct
13 Incorrect 165 ms 15864 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 7928 KB Output isn't correct
2 Incorrect 324 ms 25592 KB Output isn't correct
3 Incorrect 150 ms 21748 KB Output isn't correct
4 Runtime error 94 ms 18936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Incorrect 125 ms 10104 KB Output isn't correct
6 Incorrect 119 ms 10144 KB Output isn't correct
7 Incorrect 116 ms 9208 KB Output isn't correct
8 Incorrect 63 ms 7928 KB Output isn't correct
9 Incorrect 278 ms 25592 KB Output isn't correct
10 Incorrect 311 ms 25640 KB Output isn't correct
11 Incorrect 273 ms 25720 KB Output isn't correct
12 Incorrect 298 ms 23660 KB Output isn't correct
13 Incorrect 201 ms 25336 KB Output isn't correct
14 Incorrect 168 ms 21752 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 123 ms 14200 KB Output isn't correct
2 Incorrect 321 ms 24108 KB Output isn't correct
3 Incorrect 241 ms 23416 KB Output isn't correct
4 Incorrect 200 ms 20856 KB Output isn't correct
5 Incorrect 212 ms 20856 KB Output isn't correct
6 Incorrect 234 ms 20888 KB Output isn't correct
7 Incorrect 207 ms 19576 KB Output isn't correct
8 Incorrect 234 ms 23544 KB Output isn't correct
9 Incorrect 311 ms 26076 KB Output isn't correct
10 Incorrect 334 ms 25724 KB Output isn't correct
11 Incorrect 325 ms 25720 KB Output isn't correct
12 Incorrect 319 ms 24056 KB Output isn't correct
13 Incorrect 330 ms 28920 KB Output isn't correct
14 Incorrect 230 ms 22644 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 310 ms 25720 KB Output isn't correct
2 Incorrect 319 ms 24056 KB Output isn't correct
3 Incorrect 224 ms 28152 KB Output isn't correct
4 Incorrect 300 ms 25848 KB Output isn't correct
5 Incorrect 310 ms 25720 KB Output isn't correct
6 Incorrect 271 ms 25720 KB Output isn't correct
7 Incorrect 319 ms 24056 KB Output isn't correct
8 Incorrect 220 ms 28268 KB Output isn't correct
9 Incorrect 154 ms 21748 KB Output isn't correct