oj.uz

Submission #742262

# Submission time Handle Problem Language Result Execution time Memory
742262 2023-05-16T03:28:55 Z irmuun Ball Machine (BOI13_ballmachine) C++17
100 / 100
 380 ms 31496 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
#define pb push_back
#define ll long long
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
 
const ll N=1e5+5,log_n=17;
vector<int>adj[N],pos(N);
int n,q,root,used[N],mn[N],cur=0;
int up[N][log_n];
set<pair<int,int>>s;
vector<int>ord;
void cal(int v){
    mn[v]=v;
    for(auto u:adj[v]){
        cal(u);
        mn[v]=min(mn[u],mn[v]);
    }
}
void dfs(int v){
    vector<pair<int,int>>p;
    for(auto u:adj[v]){
        p.pb({mn[u],u});
    }
    sort(all(p));
    for(auto [val,u]:p){
        dfs(u);
    }
    ord.pb(v);
    s.insert({cur,v});
    pos[v]=cur;
    cur++;
}
int op1(){
    pair<int,int>x=*s.begin();
    used[x.ss]=1;
    s.erase(x);
    return x.ss;
}
int op2(int v){
    int x=v;
    int ans=0;
    for(int i=16;i>=0;i--){
        if(up[x][i]>-1&&used[up[x][i]]==1){
            ans+=(1<<i);
            x=up[x][i];
        }
    }
    used[x]=0;
    s.insert({pos[x],x});
    return ans;
}
 
int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        int p;
        cin>>p;
        if(p>0){
            adj[p-1].pb(i-1);
        }
        else{
            root=i-1;
        }
    }
    cal(root);
    dfs(root);
    for(int i=0;i<n;i++){
        for(int j=0;j<log_n;j++){
            up[i][j]=-1;
        }
    }
    for(int i=0;i<n;i++){
        for(auto x:adj[i]){
            up[x][0]=i;
        }
    }
    for(int j=1;j<log_n;j++){
        for(int i=0;i<n;i++){
            if(up[i][j-1]>-1&&up[up[i][j-1]][j-1]>-1){
                up[i][j]=up[up[i][j-1]][j-1];
            }
        }
    }
    while(q--){
        int t;
        cin>>t;
        if(t==1){
            int k;
            cin>>k;
            for(int i=1;i<k;i++){
                op1();
            }
            cout<<op1()+1<<"\n";
        }
        else{
            int x;
            cin>>x;
            x--;
            cout<<op2(x)<<"\n";
        }
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3028 KB Output is correct
2 Correct 266 ms 13624 KB Output is correct
3 Correct 219 ms 13384 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 4 ms 3068 KB Output is correct
6 Correct 4 ms 3156 KB Output is correct
7 Correct 4 ms 3196 KB Output is correct
8 Correct 5 ms 3156 KB Output is correct
9 Correct 19 ms 3736 KB Output is correct
10 Correct 59 ms 5612 KB Output is correct
11 Correct 258 ms 13620 KB Output is correct
12 Correct 217 ms 13472 KB Output is correct
13 Correct 251 ms 13540 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 8652 KB Output is correct
2 Correct 304 ms 24784 KB Output is correct
3 Correct 234 ms 17592 KB Output is correct
4 Correct 183 ms 9984 KB Output is correct
5 Correct 178 ms 9932 KB Output is correct
6 Correct 173 ms 9992 KB Output is correct
7 Correct 188 ms 8652 KB Output is correct
8 Correct 145 ms 8708 KB Output is correct
9 Correct 288 ms 24948 KB Output is correct
10 Correct 300 ms 24680 KB Output is correct
11 Correct 347 ms 24680 KB Output is correct
12 Correct 289 ms 21580 KB Output is correct
13 Correct 245 ms 27608 KB Output is correct
14 Correct 232 ms 17596 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 14072 KB Output is correct
2 Correct 341 ms 22000 KB Output is correct
3 Correct 220 ms 25680 KB Output is correct
4 Correct 231 ms 20512 KB Output is correct
5 Correct 197 ms 20152 KB Output is correct
6 Correct 222 ms 20236 KB Output is correct
7 Correct 201 ms 18024 KB Output is correct
8 Correct 218 ms 25636 KB Output is correct
9 Correct 332 ms 25012 KB Output is correct
10 Correct 328 ms 24796 KB Output is correct
11 Correct 336 ms 24776 KB Output is correct
12 Correct 364 ms 22032 KB Output is correct
13 Correct 334 ms 31496 KB Output is correct
14 Correct 291 ms 18688 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 25336 KB Output is correct
2 Correct 380 ms 22060 KB Output is correct
3 Correct 274 ms 30824 KB Output is correct
4 Correct 343 ms 25184 KB Output is correct
5 Correct 315 ms 24768 KB Output is correct
6 Correct 320 ms 24788 KB Output is correct
7 Correct 313 ms 22120 KB Output is correct
8 Correct 306 ms 30872 KB Output is correct
9 Correct 228 ms 17720 KB Output is correct