oj.uz

Submission #196220

# Submission time Handle Problem Language Result Execution time Memory
196220 2020-01-17T03:25:50 Z errorgorn Ball Machine (BOI13_ballmachine) C++14
7.53968 / 100
 275 ms 36000 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[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 28 ms 23800 KB Output isn't correct
2 Incorrect 173 ms 26744 KB Output isn't correct
3 Incorrect 100 ms 26748 KB Output isn't correct
4 Incorrect 27 ms 23800 KB Output isn't correct
5 Incorrect 27 ms 23800 KB Output isn't correct
6 Incorrect 28 ms 23800 KB Output isn't correct
7 Incorrect 29 ms 23800 KB Output isn't correct
8 Incorrect 28 ms 23800 KB Output isn't correct
9 Incorrect 36 ms 24056 KB Output isn't correct
10 Incorrect 60 ms 24568 KB Output isn't correct
11 Incorrect 176 ms 26868 KB Output isn't correct
12 Incorrect 101 ms 26744 KB Output isn't correct
13 Incorrect 147 ms 26844 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 26488 KB Output is correct
2 Incorrect 251 ms 31548 KB Output isn't correct
3 Incorrect 105 ms 27380 KB Output isn't correct
4 Incorrect 119 ms 26616 KB Output isn't correct
5 Incorrect 132 ms 26616 KB Output isn't correct
6 Incorrect 119 ms 26620 KB Output isn't correct
7 Incorrect 118 ms 25976 KB Output isn't correct
8 Correct 70 ms 26500 KB Output is correct
9 Incorrect 186 ms 32008 KB Output isn't correct
10 Incorrect 248 ms 31608 KB Output isn't correct
11 Incorrect 196 ms 31404 KB Output isn't correct
12 Incorrect 219 ms 29688 KB Output isn't correct
13 Correct 146 ms 34372 KB Output is correct
14 Incorrect 104 ms 27252 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 27744 KB Output isn't correct
2 Incorrect 232 ms 29920 KB Output isn't correct
3 Incorrect 182 ms 33244 KB Output isn't correct
4 Incorrect 159 ms 30044 KB Output isn't correct
5 Incorrect 170 ms 29788 KB Output isn't correct
6 Incorrect 180 ms 29688 KB Output isn't correct
7 Incorrect 197 ms 28540 KB Output isn't correct
8 Incorrect 193 ms 33232 KB Output isn't correct
9 Incorrect 275 ms 32020 KB Output isn't correct
10 Incorrect 249 ms 31548 KB Output isn't correct
11 Incorrect 247 ms 31608 KB Output isn't correct
12 Incorrect 262 ms 29924 KB Output isn't correct
13 Incorrect 253 ms 36000 KB Output isn't correct
14 Incorrect 202 ms 27644 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 234 ms 31888 KB Output isn't correct
2 Incorrect 249 ms 30024 KB Output isn't correct
3 Correct 150 ms 35540 KB Output is correct
4 Incorrect 240 ms 31932 KB Output isn't correct
5 Incorrect 266 ms 31664 KB Output isn't correct
6 Incorrect 201 ms 31484 KB Output isn't correct
7 Incorrect 245 ms 29880 KB Output isn't correct
8 Correct 156 ms 35564 KB Output is correct
9 Incorrect 105 ms 27124 KB Output isn't correct