Submission #752559

#	Time	Username	Problem	Language	Result	Execution time	Memory
752559		bgnbvnbv	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	417 ms	35248 KiB

ballmachine

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=1e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll val[maxN];
vector<ll>g[maxN];
ll P[maxN][18];
bool cmp(ll x,ll y)
{
    return val[x]<val[y];
}
void dfs(ll u,ll p)
{
    val[u]=u;
    for(int v:g[u])
    {
        dfs(v,u);
        val[u]=min(val[u],val[v]);
    }
    sort(g[u].begin(),g[u].end(),cmp);
}
ll pos[maxN],sz=0,h[maxN],cc[maxN];
void dfs2(ll u,ll p)
{
    P[u][0]=p;
    for(int i=1;i<=17;i++) P[u][i]=P[P[u][i-1]][i-1];
    for(int v:g[u])
    {
        h[v]=h[u]+1;
        dfs2(v,u);
    }
    pos[u]=++sz;
    cc[sz]=u;
}
ll n,st[4*maxN],lazy[4*maxN];
void down(ll id,ll l,ll r)
{
    ll &x=lazy[id];
    if(x!=0)
    {
        ll mid=l+r>>1;
        st[id*2]=(mid-l+1);
        lazy[id*2]=1;
        st[id*2+1]=r-mid;
        lazy[id*2+1]=1;
        x=0;
    }
}
void update(ll i,ll j,ll id=1,ll l=1,ll r=n)
{
    if(j<l||r<i) return;
    if(i<=l&&r<=j)
    {
        st[id]=(r-l+1);
        lazy[id]=1;
        return;
    }
    ll mid=l+r>>1;
    down(id,l,r);
    update(i,j,id*2,l,mid);
    update(i,j,id*2+1,mid+1,r);
    st[id]=st[id*2]+st[id*2+1];
}
void upd(ll p,ll id=1,ll l=1,ll r=n)
{
    if(l==r)
    {
        st[id]=0;
        return;
    }
    ll mid=l+r>>1;
    down(id,l,r);
    if(p<=mid) upd(p,id*2,l,mid);
    else upd(p,id*2+1,mid+1,r);
    st[id]=st[id*2]+st[id*2+1];
}
ll get(ll pos,ll id=1,ll l=1,ll r=n)
{
    if(l==r)
    {
        return st[id];
    }
    down(id,l,r);
    ll mid=l+r>>1;
    if(pos<=mid) return get(pos,id*2,l,mid);
    else return get(pos,id*2+1,mid+1,r);
}
ll s(ll k)
{
    ll l=1,r=n,id=1;
    while(true)
    {
        if(l==r)
        {
            return l;
        }
        down(id,l,r);
        ll mid=l+r>>1;
        if(mid-l+1-st[id*2]<k)
        {
            k-=mid-l+1-st[id*2];
            id=id*2+1;
            l=mid+1;
        }
        else
        {
            id=id*2;
            r=mid;
        }
    }
}
ll q;
ll r;
void solve()
{
    cin >> n >> q;
    for(int i=1;i<=n;i++)
    {
        ll p;
        cin >> p;
        if(p==0) r=i;
        else g[p].pb(i);
    }
    dfs(r,r);
    dfs2(r,r);
    while(q--)
    {
        ll t;
        cin >> t;
        if(t==1)
        {
            ll k;
            ll x;
            cin >> k;
            k=s(k);
            update(1,k);
            cout << cc[k]<<'\n';
        }
        else
        {
            ll u;
            cin >> u;
            ll x=u;
            for(int i=17;i>=0;i--)
            {
                if(get(pos[P[u][i]])==1) u=P[u][i];
            }
            cout <<h[x]-h[u]<<'\n';
            upd(pos[u]);
        }
    }
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Compilation message (stderr)

ballmachine.cpp: In function 'void down(ll, ll, ll)':
ballmachine.cpp:49:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |         ll mid=l+r>>1;
      |                ~^~
ballmachine.cpp: In function 'void update(ll, ll, ll, ll, ll)':
ballmachine.cpp:66:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |     ll mid=l+r>>1;
      |            ~^~
ballmachine.cpp: In function 'void upd(ll, ll, ll, ll)':
ballmachine.cpp:79:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   79 |     ll mid=l+r>>1;
      |            ~^~
ballmachine.cpp: In function 'll get(ll, ll, ll, ll)':
ballmachine.cpp:92:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |     ll mid=l+r>>1;
      |            ~^~
ballmachine.cpp: In function 'll s(ll)':
ballmachine.cpp:106:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |         ll mid=l+r>>1;
      |                ~^~
ballmachine.cpp: In function 'void solve()':
ballmachine.cpp:141:16: warning: unused variable 'x' [-Wunused-variable]
  141 |             ll x;
      |                ^

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