oj.uz

답안 #230399

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
230399 2020-05-10T05:23:36 Z mehrdad_sohrabi Ball Machine (BOI13_ballmachine) C++14
100 / 100
 376 ms 51736 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5248 KB Output is correct
2 Correct 206 ms 27116 KB Output is correct
3 Correct 103 ms 25972 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 7 ms 5248 KB Output is correct
6 Correct 8 ms 5504 KB Output is correct
7 Correct 9 ms 5504 KB Output is correct
8 Correct 9 ms 5504 KB Output is correct
9 Correct 17 ms 6528 KB Output is correct
10 Correct 42 ms 10616 KB Output is correct
11 Correct 198 ms 27248 KB Output is correct
12 Correct 103 ms 25968 KB Output is correct
13 Correct 173 ms 26092 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 13752 KB Output is correct
2 Correct 259 ms 43640 KB Output is correct
3 Correct 143 ms 36020 KB Output is correct
4 Correct 120 ms 17464 KB Output is correct
5 Correct 124 ms 17500 KB Output is correct
6 Correct 105 ms 16940 KB Output is correct
7 Correct 109 ms 15548 KB Output is correct
8 Correct 51 ms 13748 KB Output is correct
9 Correct 244 ms 44184 KB Output is correct
10 Correct 255 ms 43764 KB Output is correct
11 Correct 231 ms 42736 KB Output is correct
12 Correct 243 ms 40124 KB Output is correct
13 Correct 177 ms 44196 KB Output is correct
14 Correct 123 ms 36064 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 25036 KB Output is correct
2 Correct 337 ms 41968 KB Output is correct
3 Correct 221 ms 41768 KB Output is correct
4 Correct 194 ms 36592 KB Output is correct
5 Correct 187 ms 36204 KB Output is correct
6 Correct 192 ms 36088 KB Output is correct
7 Correct 214 ms 33964 KB Output is correct
8 Correct 236 ms 41888 KB Output is correct
9 Correct 346 ms 45112 KB Output is correct
10 Correct 338 ms 44724 KB Output is correct
11 Correct 349 ms 44660 KB Output is correct
12 Correct 376 ms 41844 KB Output is correct
13 Correct 359 ms 51736 KB Output is correct
14 Correct 275 ms 38492 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 345 ms 44432 KB Output is correct
2 Correct 360 ms 41396 KB Output is correct
3 Correct 198 ms 49220 KB Output is correct
4 Correct 342 ms 44320 KB Output is correct
5 Correct 316 ms 43700 KB Output is correct
6 Correct 233 ms 42676 KB Output is correct
7 Correct 306 ms 41332 KB Output is correct
8 Correct 176 ms 49224 KB Output is correct
9 Correct 134 ms 36056 KB Output is correct