oj.uz

Submission #1027065

# Submission time Handle Problem Language Result Execution time Memory
1027065 2024-07-18T20:09:48 Z hasan2006 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 316 ms 43360 KB 
#include <bits/stdc++.h>

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 1e5 + 9 , mod = 1e9 + 7;
ll  dp[N] ,  c[N] , d[N] , p[N][22] , timer = 0;
vector<int>v[N];

void dfs(int n){
    d[n] = n;
    for(auto to : v[n])
        dfs(to);
    d[p[n][0]] = min(d[p[n][0]] , d[n]);
}
set<pair<int,int>>st , ss;
void dfs1(int n){
    dp[n] = dp[p[n][0]] + 1;
    vector<pair<int,int>>vc;
    for(int i =1; i <= 20; i++)
        p[n][i] = p[p[n][i - 1]][i - 1];
    for(auto to : v[n])
    vc.pb({d[to] , to});
    sort(all(vc));
    for(auto to : vc)
        dfs1(to.se);
    c[n] = ++timer;
    st.insert({c[n] , n});
}



void solve()
{
    ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
    cin>>n>>m;
    for(i = 1; i <= n; i++){
        cin>>p[i][0];
        v[p[i][0]].pb(i);
        if(p[i][0] == 0)
            x = i;
    }
    dfs(x);
    dfs1(x);
    while(m--){
        cin>>k>>x;
        if(k == 1){
            while(x--){
                y = st.begin()->se;
                st.erase(st.begin());
            }
            cout<<y<<"\n";
        }else{
            f = x;
            for(i = 20; i >= 0; i--)
                if(p[x][i] && st.find({c[p[x][i]] , p[x][i]}) == st.end())
                    x = p[x][i];
            cout<<dp[f] - dp[x]<<"\n";
            st.insert({c[x] , x});
        }
    }
}


int main(){
    TL;

    /*#ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif*/
    int t = 1;
//    cin>>t;
    while(t--)
     {
        solve();
     }
}
// Author : حسن

Compilation message

ballmachine.cpp: In function 'void solve()':
ballmachine.cpp:50:12: warning: unused variable 'q' [-Wunused-variable]
   50 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |            ^
ballmachine.cpp:50:20: warning: unused variable 'j' [-Wunused-variable]
   50 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                    ^
ballmachine.cpp:50:23: warning: unused variable 'l' [-Wunused-variable]
   50 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                       ^
ballmachine.cpp:50:26: warning: unused variable 'r' [-Wunused-variable]
   50 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                          ^
ballmachine.cpp:50:38: warning: unused variable 's' [-Wunused-variable]
   50 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                      ^
ballmachine.cpp:50:58: warning: unused variable 'mn' [-Wunused-variable]
   50 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                          ^~
ballmachine.cpp:50:69: warning: unused variable 'mx' [-Wunused-variable]
   50 |     ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ;
      |                                                                     ^~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 115 ms 21960 KB Output is correct
3 Correct 38 ms 22220 KB Output is correct
4 Correct 1 ms 6744 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 6748 KB Output is correct
8 Correct 2 ms 6748 KB Output is correct
9 Correct 6 ms 7004 KB Output is correct
10 Correct 18 ms 9816 KB Output is correct
11 Correct 94 ms 21920 KB Output is correct
12 Correct 52 ms 22100 KB Output is correct
13 Correct 81 ms 21852 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12792 KB Output is correct
2 Correct 239 ms 35480 KB Output is correct
3 Correct 71 ms 28616 KB Output is correct
4 Correct 79 ms 15188 KB Output is correct
5 Correct 124 ms 15440 KB Output is correct
6 Correct 107 ms 15188 KB Output is correct
7 Correct 104 ms 14160 KB Output is correct
8 Correct 32 ms 12888 KB Output is correct
9 Correct 188 ms 35808 KB Output is correct
10 Correct 249 ms 35412 KB Output is correct
11 Correct 194 ms 35412 KB Output is correct
12 Correct 222 ms 32080 KB Output is correct
13 Correct 83 ms 40528 KB Output is correct
14 Correct 49 ms 28616 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 22124 KB Output is correct
2 Correct 227 ms 32556 KB Output is correct
3 Correct 139 ms 36432 KB Output is correct
4 Correct 146 ms 30712 KB Output is correct
5 Correct 169 ms 30680 KB Output is correct
6 Correct 163 ms 30540 KB Output is correct
7 Correct 164 ms 27984 KB Output is correct
8 Correct 150 ms 36500 KB Output is correct
9 Correct 189 ms 35892 KB Output is correct
10 Correct 316 ms 35708 KB Output is correct
11 Correct 285 ms 35588 KB Output is correct
12 Correct 297 ms 32596 KB Output is correct
13 Correct 248 ms 43360 KB Output is correct
14 Correct 86 ms 28812 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 35920 KB Output is correct
2 Correct 222 ms 32596 KB Output is correct
3 Correct 93 ms 43048 KB Output is correct
4 Correct 190 ms 35924 KB Output is correct
5 Correct 278 ms 35744 KB Output is correct
6 Correct 213 ms 35548 KB Output is correct
7 Correct 247 ms 32596 KB Output is correct
8 Correct 102 ms 43092 KB Output is correct
9 Correct 52 ms 28616 KB Output is correct