Submission #230399

#	Time	Username	Problem	Language	Result	Execution time	Memory
230399		mehrdad_sohrabi	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	376 ms	51736 KiB

ballmachine

#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
/// khodaya komak kon
/// ya navid navid
const int N=2e5+100,M=22;
vector <int> g[N],a;
ll st[N],fn[N],ts=1,lazy[N*4],mi[N],par[N][M];
void shift(ll nod){
    lazy[nod*2]+=lazy[nod];
    lazy[nod*2+1]+=lazy[nod];
    lazy[nod]=0;
}
void upd(ll nod,ll l,ll r,ll L,ll R,ll val){
    if (l>=R || L>=r) return ;
    if (l>=L && r<=R){
        lazy[nod]+=val;
        return ;
    }
    shift(nod);
    ll mid=(r+l)/2;
    upd(nod*2,l,mid,L,R,val);
    upd(nod*2+1,mid,r,L,R,val);
}
ll get(ll nod,ll l,ll r,ll id){
    if (r-l==1) return lazy[nod];
    shift(nod);
    ll mid=(r+l)/2;
    if (mid>id) return get(nod*2,l,mid,id);
    else return get(nod*2+1,mid,r,id);
}
ll hi[N];
ll dfsh(ll v,ll p,ll h){
    //sub[v]=1;
    hi[v]=h;
    for (int i=0;i<g[v].size();i++){
        ll u=g[v][i];
        if (u!=p){
            par[u][0]=v;
            dfsh(u,v,h+1);
           // sub[v]+=sub[u];
        }
    }
   // return sub[v];
}
ll dfs1(ll v,ll p){
    vector <pii> b;
    for (int u: g[v]){
        if (u==p) continue;
        b.pb({mi[u],u});
    }
    sort(b.begin(),b.end());
    for (int i=0;i<b.size();i++){
        ll u=b[i].S;
        dfs1(u,v);
    }
    a.pb(v);
}
ll dfs(ll v,ll p){
    st[v]=ts;
    mi[v]=v;
    for (auto u : g[v]){
        if (u==p) continue;
        ts++;
        dfs(u,v);
        mi[v]=min(mi[v],mi[u]);
    }
    fn[v]=ts;
}
ll getpar(ll v,ll h){
    if (h==-1 || h==0){
        return v;
    }
    for(int i=0;i<M;i++){
        if (h & (1 << i)) v = par[v][i];
    }
    return v;
}
ll val[N];
int32_t main(){
    sync;
    ll n,q;
    cin >> n >> q;
    ll root=0;
    for (int i=1;i<=n;i++){
        ll p;
        cin >> p;
        if (p==0){
            root=i;
            continue;
        }
        g[p].pb(i);
    }
    a.pb(0);
    dfs(root,0);
    dfs1(root,0);
    dfsh(root,0,1);
    par[root][0]=root;
    for (int i=1;i<M;i++){
        for (int j=1;j<=n;j++){
            par[j][i]=par[par[j][i-1]][i-1];
        }
    }
    ll cnt=0;
    set <pii> s;
    for (int i=1;i<=n;i++){
        s.insert({i,a[i]});
        val[a[i]]=i;
    }
    while(q--){
        ll t;
        cin >> t;
        if (t==1){
            ll k;
            cin >> k;
            ll v=0;
            while(k){
                v=s.begin()->S;
                s.erase(s.begin());
                upd(1,1,N,st[v],fn[v]+1,1);
                k--;
            }
            cout << v << endl;
        }
        else{
            ll x;
            cin >> x;
            ll z=get(1,1,N,st[x])-1;
            cout << z << endl;
            ll v=getpar(x,z);
            s.insert({val[v],v});
            upd(1,1,N,st[v],fn[v]+1,-1);

         }
    }

}

Compilation message (stderr)

ballmachine.cpp: In function 'll dfsh(ll, ll, ll)':
ballmachine.cpp:47:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<g[v].size();i++){
                  ~^~~~~~~~~~~~
ballmachine.cpp:56:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
ballmachine.cpp: In function 'll dfs1(ll, ll)':
ballmachine.cpp:64:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<b.size();i++){
                  ~^~~~~~~~~
ballmachine.cpp:69:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
ballmachine.cpp: In function 'll dfs(ll, ll)':
ballmachine.cpp:80:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
ballmachine.cpp: In function 'int32_t main()':
ballmachine.cpp:115:8: warning: unused variable 'cnt' [-Wunused-variable]
     ll cnt=0;
        ^~~

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