Submission #1027065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027065		hasan2006	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	316 ms	43360 KiB

ballmachine

#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 (stderr)

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 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5