Submission #196861

#	Time	Username	Problem	Language	Result	Execution time	Memory
196861		errorgorn	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	293 ms	31096 KiB

ballmachine

#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][20];
vector<int> al[100005];

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

bool filled[100005];

int counter=0;

int small[100005];
int dfs_pre(int i,int p){
    small[i]=i;
    for (auto &it:al[i]){
        if (it==p) continue;
        small[i]=min(small[i],dfs_pre(it,i));
    }
    return small[i];
}

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);
        }
    }
    
    dfs_pre(__root,-1);
    for (int x=1;x<=n;x++) sort(al[x].begin(),al[x].end(),[](int i,int j){
        return small[i]<small[j];
    });
    
    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 (stderr)

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:77: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:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&temp);
         ~~~~~^~~~~~~~~~~~
ballmachine.cpp:102: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:109:19: warning: 'high' may be used uninitialized in this function [-Wmaybe-uninitialized]
             printf("%d\n",pos[high]);
             ~~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5