oj.uz

Submission #742263

# Submission time Handle Problem Language Result Execution time Memory
742263 2023-05-16T03:29:40 Z irmuun Ball Machine (BOI13_ballmachine) C++17
100 / 100
 194 ms 30300 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(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    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 2 ms 3028 KB Output is correct
2 Correct 111 ms 12568 KB Output is correct
3 Correct 60 ms 12504 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 3 ms 3156 KB Output is correct
7 Correct 3 ms 3156 KB Output is correct
8 Correct 3 ms 3156 KB Output is correct
9 Correct 7 ms 3760 KB Output is correct
10 Correct 31 ms 5516 KB Output is correct
11 Correct 94 ms 12592 KB Output is correct
12 Correct 61 ms 12488 KB Output is correct
13 Correct 105 ms 12696 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 8316 KB Output is correct
2 Correct 138 ms 23468 KB Output is correct
3 Correct 90 ms 16764 KB Output is correct
4 Correct 67 ms 9604 KB Output is correct
5 Correct 60 ms 9380 KB Output is correct
6 Correct 52 ms 9348 KB Output is correct
7 Correct 56 ms 8088 KB Output is correct
8 Correct 41 ms 8388 KB Output is correct
9 Correct 119 ms 23680 KB Output is correct
10 Correct 131 ms 23420 KB Output is correct
11 Correct 113 ms 23352 KB Output is correct
12 Correct 142 ms 20296 KB Output is correct
13 Correct 94 ms 26776 KB Output is correct
14 Correct 79 ms 16856 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 13496 KB Output is correct
2 Correct 162 ms 20864 KB Output is correct
3 Correct 110 ms 24880 KB Output is correct
4 Correct 104 ms 19652 KB Output is correct
5 Correct 112 ms 19504 KB Output is correct
6 Correct 94 ms 19400 KB Output is correct
7 Correct 107 ms 17272 KB Output is correct
8 Correct 113 ms 24876 KB Output is correct
9 Correct 170 ms 23860 KB Output is correct
10 Correct 154 ms 23616 KB Output is correct
11 Correct 162 ms 23668 KB Output is correct
12 Correct 175 ms 20812 KB Output is correct
13 Correct 156 ms 30300 KB Output is correct
14 Correct 149 ms 17268 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 23952 KB Output is correct
2 Correct 145 ms 20876 KB Output is correct
3 Correct 112 ms 29748 KB Output is correct
4 Correct 189 ms 24000 KB Output is correct
5 Correct 147 ms 23644 KB Output is correct
6 Correct 120 ms 23544 KB Output is correct
7 Correct 175 ms 20852 KB Output is correct
8 Correct 108 ms 29892 KB Output is correct
9 Correct 89 ms 16820 KB Output is correct