oj.uz

Submission #196833

# Submission time Handle Problem Language Result Execution time Memory
196833 2020-01-17T05:23:05 Z errorgorn Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 321 ms 34680 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 28 ms 23800 KB Output isn't correct
2 Incorrect 171 ms 25720 KB Output isn't correct
3 Incorrect 100 ms 25848 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 28 ms 23800 KB Output isn't correct
8 Incorrect 28 ms 23792 KB Output isn't correct
9 Incorrect 34 ms 23928 KB Output isn't correct
10 Incorrect 53 ms 24312 KB Output isn't correct
11 Incorrect 203 ms 25608 KB Output isn't correct
12 Incorrect 101 ms 25852 KB Output isn't correct
13 Incorrect 161 ms 25640 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 25976 KB Output is correct
2 Incorrect 234 ms 30328 KB Output isn't correct
3 Incorrect 104 ms 26560 KB Output isn't correct
4 Incorrect 117 ms 25848 KB Output isn't correct
5 Incorrect 120 ms 25720 KB Output isn't correct
6 Incorrect 114 ms 25848 KB Output isn't correct
7 Incorrect 113 ms 25128 KB Output isn't correct
8 Correct 68 ms 25976 KB Output is correct
9 Incorrect 186 ms 30448 KB Output isn't correct
10 Incorrect 228 ms 30204 KB Output isn't correct
11 Incorrect 184 ms 30072 KB Output isn't correct
12 Incorrect 204 ms 28372 KB Output isn't correct
13 Correct 133 ms 33272 KB Output is correct
14 Incorrect 105 ms 26356 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 27144 KB Output isn't correct
2 Incorrect 268 ms 28524 KB Output isn't correct
3 Correct 158 ms 32348 KB Output is correct
4 Incorrect 186 ms 29176 KB Output isn't correct
5 Incorrect 211 ms 28880 KB Output isn't correct
6 Incorrect 204 ms 28792 KB Output isn't correct
7 Incorrect 200 ms 27512 KB Output isn't correct
8 Correct 222 ms 32596 KB Output is correct
9 Incorrect 224 ms 30504 KB Output isn't correct
10 Incorrect 238 ms 30280 KB Output isn't correct
11 Incorrect 245 ms 30200 KB Output isn't correct
12 Incorrect 229 ms 28536 KB Output isn't correct
13 Correct 321 ms 34680 KB Output is correct
14 Incorrect 211 ms 26220 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 225 ms 30704 KB Output isn't correct
2 Incorrect 225 ms 28668 KB Output isn't correct
3 Correct 148 ms 34424 KB Output is correct
4 Incorrect 228 ms 30812 KB Output isn't correct
5 Incorrect 240 ms 30200 KB Output isn't correct
6 Incorrect 238 ms 30172 KB Output isn't correct
7 Incorrect 229 ms 28720 KB Output isn't correct
8 Correct 146 ms 34544 KB Output is correct
9 Incorrect 104 ms 26436 KB Output isn't correct