oj.uz

Submission #196831

# Submission time Handle Problem Language Result Execution time Memory
196831 2020-01-17T05:18:36 Z errorgorn Ball Machine (BOI13_ballmachine) C++14
0 / 100
 308 ms 36076 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(1,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 28 ms 23800 KB Output isn't correct
2 Incorrect 172 ms 26756 KB Output isn't correct
3 Incorrect 101 ms 26828 KB Output isn't correct
4 Incorrect 27 ms 23800 KB Output isn't correct
5 Incorrect 28 ms 23800 KB Output isn't correct
6 Incorrect 18 ms 23772 KB Output isn't correct
7 Incorrect 28 ms 23800 KB Output isn't correct
8 Incorrect 28 ms 23852 KB Output isn't correct
9 Incorrect 34 ms 23928 KB Output isn't correct
10 Incorrect 51 ms 24440 KB Output isn't correct
11 Incorrect 167 ms 26884 KB Output isn't correct
12 Incorrect 99 ms 26744 KB Output isn't correct
13 Incorrect 146 ms 26744 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 26488 KB Output isn't correct
2 Incorrect 230 ms 31540 KB Output isn't correct
3 Incorrect 101 ms 27380 KB Output isn't correct
4 Incorrect 116 ms 26620 KB Output isn't correct
5 Incorrect 121 ms 26528 KB Output isn't correct
6 Incorrect 113 ms 26656 KB Output isn't correct
7 Incorrect 113 ms 25908 KB Output isn't correct
8 Incorrect 70 ms 26488 KB Output isn't correct
9 Incorrect 244 ms 31864 KB Output isn't correct
10 Incorrect 245 ms 31568 KB Output isn't correct
11 Incorrect 181 ms 31408 KB Output isn't correct
12 Incorrect 230 ms 29800 KB Output isn't correct
13 Incorrect 135 ms 34304 KB Output isn't correct
14 Incorrect 107 ms 27372 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 27872 KB Output isn't correct
2 Incorrect 246 ms 29936 KB Output isn't correct
3 Incorrect 171 ms 33272 KB Output isn't correct
4 Incorrect 152 ms 30184 KB Output isn't correct
5 Incorrect 156 ms 29708 KB Output isn't correct
6 Incorrect 159 ms 29724 KB Output isn't correct
7 Incorrect 162 ms 28456 KB Output isn't correct
8 Incorrect 166 ms 33304 KB Output isn't correct
9 Incorrect 229 ms 32060 KB Output isn't correct
10 Incorrect 234 ms 31452 KB Output isn't correct
11 Incorrect 243 ms 31412 KB Output isn't correct
12 Incorrect 249 ms 29944 KB Output isn't correct
13 Incorrect 308 ms 36076 KB Output isn't correct
14 Incorrect 196 ms 27708 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 256 ms 31976 KB Output isn't correct
2 Incorrect 283 ms 29852 KB Output isn't correct
3 Incorrect 164 ms 35644 KB Output isn't correct
4 Incorrect 227 ms 32056 KB Output isn't correct
5 Incorrect 235 ms 31456 KB Output isn't correct
6 Incorrect 196 ms 31464 KB Output isn't correct
7 Incorrect 278 ms 29908 KB Output isn't correct
8 Incorrect 147 ms 35592 KB Output isn't correct
9 Incorrect 102 ms 27384 KB Output isn't correct