oj.uz

답안 #196861

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
196861 2020-01-17T10:16:10 Z errorgorn Ball Machine (BOI13_ballmachine) C++14
100 / 100
 293 ms 31096 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][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

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.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 24 ms 19832 KB Output is correct
2 Correct 161 ms 22008 KB Output is correct
3 Correct 91 ms 22136 KB Output is correct
4 Correct 24 ms 19960 KB Output is correct
5 Correct 23 ms 19960 KB Output is correct
6 Correct 24 ms 19964 KB Output is correct
7 Correct 24 ms 19960 KB Output is correct
8 Correct 24 ms 19960 KB Output is correct
9 Correct 31 ms 19960 KB Output is correct
10 Correct 49 ms 20472 KB Output is correct
11 Correct 214 ms 21980 KB Output is correct
12 Correct 105 ms 22088 KB Output is correct
13 Correct 142 ms 21944 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 22224 KB Output is correct
2 Correct 241 ms 26512 KB Output is correct
3 Correct 120 ms 22772 KB Output is correct
4 Correct 111 ms 22204 KB Output is correct
5 Correct 113 ms 22164 KB Output is correct
6 Correct 99 ms 21992 KB Output is correct
7 Correct 105 ms 21368 KB Output is correct
8 Correct 65 ms 22064 KB Output is correct
9 Correct 183 ms 26948 KB Output is correct
10 Correct 210 ms 26488 KB Output is correct
11 Correct 239 ms 26500 KB Output is correct
12 Correct 228 ms 24848 KB Output is correct
13 Correct 154 ms 29688 KB Output is correct
14 Correct 103 ms 22644 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 110 ms 23480 KB Output is correct
2 Correct 232 ms 24960 KB Output is correct
3 Correct 190 ms 28920 KB Output is correct
4 Correct 149 ms 25612 KB Output is correct
5 Correct 166 ms 25312 KB Output is correct
6 Correct 220 ms 25212 KB Output is correct
7 Correct 210 ms 23912 KB Output is correct
8 Correct 162 ms 28712 KB Output is correct
9 Correct 293 ms 27000 KB Output is correct
10 Correct 282 ms 26720 KB Output is correct
11 Correct 223 ms 26616 KB Output is correct
12 Correct 239 ms 25028 KB Output is correct
13 Correct 244 ms 31096 KB Output is correct
14 Correct 196 ms 22772 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 224 ms 27184 KB Output is correct
2 Correct 231 ms 25092 KB Output is correct
3 Correct 162 ms 30840 KB Output is correct
4 Correct 250 ms 27224 KB Output is correct
5 Correct 235 ms 26744 KB Output is correct
6 Correct 175 ms 26488 KB Output is correct
7 Correct 235 ms 25016 KB Output is correct
8 Correct 159 ms 31096 KB Output is correct
9 Correct 113 ms 22644 KB Output is correct