Submission #575308

#	Time	Username	Problem	Language	Result	Execution time	Memory
575308		ktkerem	Ball Machine (BOI13_ballmachine)	C++17	0 / 100	1097 ms	131072 KiB

ballmachine

/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")*/
#include<bits/stdc++.h>
/*#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
template<class T>
using oset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
/**/
//typedef int ll;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 vll;
typedef unsigned __int128 uvll;
ll _i=0;
#define ffn(x) _i=x
#define llll std::pair<ll , ll>
#define stitr set<ll>::iterator
#define fora(y,x) for(ll y=_i;x>y;y++)
#define pb push_back
#define pf push_front
#define halo cout << "hello\n"
#define fi first
#define sec second
#define all(a) a.begin() , a.end()
const ll limit = 1e9 + 7; 
const ll ous = 1e5 + 7;
const ll dx[4] = {1 , 0 , 0 , -1} , dy[4] = {0,1,-1,0};
#define LOGN 17 // will work for n <= 100.000
ll n, q;
ll par[LOGN][ous];
std::vector<ll> adj[ous];
std::vector<ll> low (ous , ous);
std::vector<ll> post (ous , 0);
std::vector<bool> ball(ous , 0);
std::vector<ll> layer(ous , 0);
ll root;
bool cmpLow(ll a, ll b) { return low[a] < low[b]; }
bool cmpPostInv(ll a, ll b) { return post[a] > post[b]; }
std::priority_queue<ll, std::vector<ll>, bool(*)(ll,ll)> pepsi(cmpPostInv);
void fdfs(ll v){   
    if(v == root){
        layer[v] = 0;
    }
    else{
        layer[v] = layer[par[0][v]] + 1;
    }
    low[v] = v;
    for(auto j:adj[v]){
        fdfs(j);
        low[v] = std::min(low[v] , low[j]);
    }
}
ll t;
void sdfs(ll v){
    for(auto j:adj[v]){
        sdfs(j);
    }
    post[v] = t++;
}
ll add(){
    ll tk = pepsi.top();
    pepsi.pop();
    ball[tk] = true;
    return tk;
}
ll remove(ll x){
    for(ll lev = LOGN - 1;lev >= 0;lev--){
        if(ball[par[lev][x]]){
            x = par[lev][x];
        }
    }
    ball[x] = false;
    pepsi.push(x);
    return x;
}
void solve(){
    std::cin >> n >> q;
    fora(i , n){
        ll x;std::cin >> x;
        if(x == 0){
            continue;
        
        }
        else{
            par[0][i] = x - 1;    
        }
    }
    fora(i , n){
        if(par[0][i] == i){
            root = i;
        }
        else{
            adj[par[0][i]].pb(i);
        }
    }
    par[0][root] = root;
    for(ll lev = 1;LOGN > lev;lev++){
        fora(i , n){
            par[lev][i] = par[lev - 1][par[lev - 1][i]];
        }
    }
    fdfs(root);
    fora(i , n){
        std::sort(all(adj[i]) , cmpLow);
    }
    sdfs(root);
    fora(i , n){
        pepsi.push(i);
    }
    fora(i , q){
        ll x , y;std::cin >> x >> y;
        if(x == 1){
            ll pos = 0;
            fora(j , y){
                pos = add();
            }
            std::cout << pos + 1 << "\n";
        }
        else if(x == 2){
            ll pos = 0;
            y--;
            pos = remove(y);
            std::cout << layer[y] - layer[pos] << "\n";
        }
    }
    return;/**/
}
signed main(){
    std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
    ll t=1;
    //std::cin >> t;
    ll o = 1;
    while(t--){ 
        //cout << "Case " << o++ << ":\n";
        solve();
    }
    return 0; 
}

Compilation message (stderr)

ballmachine.cpp:12:1: warning: "/*" within comment [-Wcomment]
   12 | /**/
      |  
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:136:8: warning: unused variable 'o' [-Wunused-variable]
  136 |     ll o = 1;
      |        ^

• Subtask 1: 0 / 25
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40
• Subtask 4: 0 / 5