oj.uz

답안 #752559

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
752559 2023-06-03T08:15:57 Z bgnbvnbv Ball Machine (BOI13_ballmachine) C++14
100 / 100
 417 ms 35248 KB 
#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

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.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 174 ms 17912 KB Output is correct
3 Correct 79 ms 16364 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 2 ms 2900 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 3 ms 2900 KB Output is correct
9 Correct 12 ms 3688 KB Output is correct
10 Correct 25 ms 6484 KB Output is correct
11 Correct 164 ms 17864 KB Output is correct
12 Correct 102 ms 16344 KB Output is correct
13 Correct 122 ms 16560 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 8280 KB Output is correct
2 Correct 287 ms 29308 KB Output is correct
3 Correct 97 ms 22668 KB Output is correct
4 Correct 123 ms 11340 KB Output is correct
5 Correct 151 ms 11236 KB Output is correct
6 Correct 133 ms 10444 KB Output is correct
7 Correct 130 ms 9988 KB Output is correct
8 Correct 72 ms 8396 KB Output is correct
9 Correct 249 ms 29440 KB Output is correct
10 Correct 271 ms 29292 KB Output is correct
11 Correct 267 ms 26972 KB Output is correct
12 Correct 261 ms 26500 KB Output is correct
13 Correct 148 ms 27596 KB Output is correct
14 Correct 97 ms 22620 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 16980 KB Output is correct
2 Correct 319 ms 29256 KB Output is correct
3 Correct 188 ms 28244 KB Output is correct
4 Correct 154 ms 25296 KB Output is correct
5 Correct 193 ms 24804 KB Output is correct
6 Correct 213 ms 24912 KB Output is correct
7 Correct 186 ms 23576 KB Output is correct
8 Correct 202 ms 28360 KB Output is correct
9 Correct 300 ms 31308 KB Output is correct
10 Correct 417 ms 30848 KB Output is correct
11 Correct 329 ms 30848 KB Output is correct
12 Correct 301 ms 29408 KB Output is correct
13 Correct 312 ms 35248 KB Output is correct
14 Correct 150 ms 27104 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 276 ms 29708 KB Output is correct
2 Correct 327 ms 28124 KB Output is correct
3 Correct 181 ms 30772 KB Output is correct
4 Correct 234 ms 29684 KB Output is correct
5 Correct 312 ms 29220 KB Output is correct
6 Correct 238 ms 26872 KB Output is correct
7 Correct 295 ms 28240 KB Output is correct
8 Correct 159 ms 30860 KB Output is correct
9 Correct 92 ms 22632 KB Output is correct