oj.uz

Submission #196246

# Submission time Handle Problem Language Result Execution time Memory
196246 2020-01-17T03:31:02 Z errorgorn Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 287 ms 34692 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

struct node{
    int s,e,m;
    bool empty=true;
    node *l,*r;
    
    node (int _s,int _e){
        s=_s,e=_e,m=s+e>>1;
        
        if (s!=e){
            l=new node(s,m);
            r=new node(m+1,e);
        }
    }
    
    void update(int i){
        if (s==e) empty^=true;
        else{
            if (i<=m) l->update(i);
            else r->update(i);
            
            empty=l->empty||r->empty;
        }
    }
    
    int query(){
        if (s==e) return s;
        else{
            if (l->empty) l->query();
            else r->query();
        }
    }
} *root=new node(0,100005);

int n,q;
int __root;
int parent[100005][30];
vector<int> al[100005];

int pos[100005];
int perm[100005];

bool filled[100005];

int counter=0;
void dfs(int i,int p){
    int curr;
    for (auto &it:al[i]){
        if (it==p) continue;
        curr=parent[it][0]=i;
        for (int x=0;parent[curr][x]!=-1;x++){
            curr=parent[it][x+1]=parent[curr][x];
        }
        dfs(it,i);
    }
    pos[counter]=i;
    perm[i]=counter++;
}

int main(){
    scanf("%d%d",&n,&q);
    
    int temp;
    for (int x=1;x<=n;x++){
        scanf("%d",&temp);
        if (temp==0){
            __root=x;
        }
        else{
            al[temp].push_back(x);
        }
    }
    
    for (int x=1;x<=n;x++) sort(al[x].begin(),al[x].end());
    
    memset(parent,-1,sizeof(parent));
    dfs(__root,-1);
    
    int a,b;
    int high;
    int nums;
    while (q--){
        scanf("%d%d",&a,&b);
        if (a==1){
            for (int x=0;x<b;x++){
                high=root->query();
                filled[pos[high]]=true;
                root->update(high);
            }
            printf("%d\n",pos[high]);
        }
        else{
            high=b;
            nums=0;
            for (int x=19;~x;x--){
                if (parent[high][x]!=-1 && filled[parent[high][x]]) high=parent[high][x],nums|=(1<<x);
            }
            
            filled[high]=false;
            root->update(perm[high]);
            printf("%d\n",nums);
        }
    }
    
    
}

Compilation message

ballmachine.cpp: In constructor 'node::node(int, int)':
ballmachine.cpp:13:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         s=_s,e=_e,m=s+e>>1;
                     ~^~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&q);
     ~~~~~^~~~~~~~~~~~~~
ballmachine.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&temp);
         ~~~~~^~~~~~~~~~~~
ballmachine.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~
ballmachine.cpp: In member function 'int node::query()':
ballmachine.cpp:37:5: warning: control reaches end of non-void function [-Wreturn-type]
     }
     ^
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:95:19: warning: 'high' may be used uninitialized in this function [-Wmaybe-uninitialized]
             printf("%d\n",pos[high]);
             ~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 23800 KB Output isn't correct
2 Incorrect 208 ms 25648 KB Output isn't correct
3 Incorrect 107 ms 25820 KB Output isn't correct
4 Incorrect 28 ms 23800 KB Output isn't correct
5 Incorrect 28 ms 23800 KB Output isn't correct
6 Incorrect 26 ms 23856 KB Output isn't correct
7 Incorrect 29 ms 23796 KB Output isn't correct
8 Incorrect 29 ms 23800 KB Output isn't correct
9 Incorrect 36 ms 23956 KB Output isn't correct
10 Incorrect 49 ms 24184 KB Output isn't correct
11 Incorrect 175 ms 25792 KB Output isn't correct
12 Incorrect 104 ms 25796 KB Output isn't correct
13 Incorrect 155 ms 25672 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 26076 KB Output is correct
2 Incorrect 246 ms 30224 KB Output isn't correct
3 Incorrect 106 ms 26496 KB Output isn't correct
4 Incorrect 118 ms 25884 KB Output isn't correct
5 Incorrect 123 ms 25948 KB Output isn't correct
6 Incorrect 113 ms 25872 KB Output isn't correct
7 Incorrect 117 ms 25236 KB Output isn't correct
8 Correct 71 ms 25976 KB Output is correct
9 Incorrect 219 ms 30524 KB Output isn't correct
10 Incorrect 240 ms 30200 KB Output isn't correct
11 Incorrect 188 ms 30076 KB Output isn't correct
12 Incorrect 213 ms 28408 KB Output isn't correct
13 Correct 156 ms 33284 KB Output is correct
14 Incorrect 110 ms 26456 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 27192 KB Output isn't correct
2 Incorrect 238 ms 28428 KB Output isn't correct
3 Correct 165 ms 32376 KB Output is correct
4 Incorrect 156 ms 29148 KB Output isn't correct
5 Incorrect 171 ms 28832 KB Output isn't correct
6 Incorrect 165 ms 28920 KB Output isn't correct
7 Incorrect 157 ms 27568 KB Output isn't correct
8 Correct 166 ms 32364 KB Output is correct
9 Incorrect 228 ms 30588 KB Output isn't correct
10 Incorrect 240 ms 30368 KB Output isn't correct
11 Incorrect 238 ms 30072 KB Output isn't correct
12 Incorrect 235 ms 28792 KB Output isn't correct
13 Correct 243 ms 34692 KB Output is correct
14 Incorrect 196 ms 26228 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 246 ms 30620 KB Output isn't correct
2 Incorrect 228 ms 28592 KB Output isn't correct
3 Correct 153 ms 34532 KB Output is correct
4 Incorrect 287 ms 30712 KB Output isn't correct
5 Incorrect 236 ms 30200 KB Output isn't correct
6 Incorrect 226 ms 30380 KB Output isn't correct
7 Incorrect 249 ms 28568 KB Output isn't correct
8 Correct 145 ms 34424 KB Output is correct
9 Incorrect 102 ms 26228 KB Output isn't correct