oj.uz

Submission #521163

# Submission time Handle Problem Language Result Execution time Memory
521163 2022-02-01T06:11:53 Z krit3379 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 344 ms 33872 KB 
#include<bits/stdc++.h>
using namespace std;
#define N 100005

int t[4*N],lazy[4*N];
int root,bp[20][N],h[N],st[N],en[N],sub_sz[N],sub_mi[N],prior[N],sz,p,ll,rr,val;
vector<int> g[N];
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;

void push(int x){
    if(lazy[x]){
        t[x*2]=t[x*2+1]=lazy[x*2]=lazy[x*2+1]=lazy[x];
        lazy[x]=0;
    }
}

void update(int x,int l,int r){
    if(r<ll||rr<l)return ;
    if(ll<=l&&r<=rr){
        t[x]=val;
        lazy[x]=val;
        return ;
    }
    push(x);
    int mid=(l+r)/2;
    update(x*2,l,mid);
    update(x*2+1,mid+1,r);
}

int sol(int x,int l,int r){
    if(r<ll||rr<l)return -1;
    if(ll<=l&&r<=rr)return t[x];
    push(x);
    int mid=(l+r)/2;
    return max(sol(x*2,l,mid),sol(x*2+1,mid+1,r));
}

void dfs(int s,int f){
    bp[0][s]=f;
    st[s]=en[s]=++sz;
    sub_sz[s]=1;
    sub_mi[s]=s;
    h[s]=h[f]+1;
    for(auto x:g[s]){
        dfs(x,s);
        en[s]=en[x];
        sub_mi[s]=min(sub_mi[s],sub_mi[x]);
        sub_sz[s]+=sub_sz[x];
    }
}

void up_pri(int s){
    vector<pair<int,int>> temp;
    for(auto x:g[s])temp.push_back({sub_mi[x],x});
    sort(temp.begin(),temp.end());
    for(auto x:temp){
        up_pri(x.second);
    }
    prior[s]=++p;
}

int main(){
    int n,m,i,j,op,k,x;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&k);
        g[k].push_back(i);
        if(k==0)root=i;
    }
    dfs(root,0);
    up_pri(root);
    for(i=1;i<=n;i++)q.push({prior[i],i});
    for(i=1;i<20;i++)for(j=1;j<=n;j++)bp[i][j]=bp[i-1][bp[i-1][j]];
    while(m--){
        scanf("%d %d",&op,&k);
        if(op==1){
            while(k--){
                x=q.top().second;
                q.pop();
                ll=st[x],rr=en[x];
                val=h[x];
                update(1,1,n);
            }
            printf("%d\n",x);
        }
        else{
            ll=rr=st[k];
            val=sol(1,1,n);
            printf("%d\n",h[k]-val);
            if(h[k]!=val){
                for(i=19;i>=0;i--)if(h[bp[i][k]]>val)k=bp[i][k];
                k=bp[0][k];
            }
            q.push({prior[k],k});
            ll=st[k],rr=en[k];
            val=h[k]+1;
            update(1,1,n);
            ll=st[k],rr=st[k];
            val=0;
            update(1,1,n);
        }
    }

    return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
ballmachine.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         scanf("%d",&k);
      |         ~~~~~^~~~~~~~~
ballmachine.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf("%d %d",&op,&k);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2764 KB Output is correct
2 Correct 205 ms 13212 KB Output is correct
3 Correct 72 ms 12368 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 3 ms 2780 KB Output is correct
6 Correct 3 ms 2912 KB Output is correct
7 Correct 4 ms 2892 KB Output is correct
8 Correct 3 ms 2912 KB Output is correct
9 Correct 11 ms 3436 KB Output is correct
10 Correct 32 ms 5452 KB Output is correct
11 Correct 204 ms 13240 KB Output is correct
12 Correct 69 ms 12356 KB Output is correct
13 Correct 178 ms 12508 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 8668 KB Output is correct
2 Correct 172 ms 25540 KB Output is correct
3 Correct 80 ms 16236 KB Output is correct
4 Correct 93 ms 10264 KB Output is correct
5 Correct 93 ms 10164 KB Output is correct
6 Correct 90 ms 9828 KB Output is correct
7 Correct 109 ms 8560 KB Output is correct
8 Correct 47 ms 8452 KB Output is correct
9 Correct 167 ms 25788 KB Output is correct
10 Correct 173 ms 25540 KB Output is correct
11 Correct 196 ms 24568 KB Output is correct
12 Correct 179 ms 21416 KB Output is correct
13 Correct 107 ms 28356 KB Output is correct
14 Correct 80 ms 16180 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 14812 KB Output is correct
2 Correct 291 ms 22852 KB Output is correct
3 Correct 169 ms 27408 KB Output is correct
4 Correct 175 ms 21956 KB Output is correct
5 Correct 152 ms 21572 KB Output is correct
6 Correct 149 ms 21488 KB Output is correct
7 Correct 178 ms 18708 KB Output is correct
8 Correct 186 ms 27420 KB Output is correct
9 Correct 284 ms 26772 KB Output is correct
10 Correct 262 ms 26404 KB Output is correct
11 Correct 265 ms 26436 KB Output is correct
12 Correct 277 ms 22864 KB Output is correct
13 Correct 301 ms 33872 KB Output is correct
14 Correct 202 ms 18516 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 26052 KB Output is correct
2 Correct 286 ms 22344 KB Output is correct
3 Correct 120 ms 31632 KB Output is correct
4 Correct 344 ms 26000 KB Output is correct
5 Correct 288 ms 25704 KB Output is correct
6 Correct 252 ms 24448 KB Output is correct
7 Correct 252 ms 22388 KB Output is correct
8 Correct 126 ms 31556 KB Output is correct
9 Correct 85 ms 16216 KB Output is correct