oj.uz

답안 #58559

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
58559 2018-07-18T07:41:26 Z Batrr Ball Machine (BOI13_ballmachine) C++14
100 / 100
 647 ms 35444 KB 
#include <bits/stdc++.h>
/*
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
*/
#define ll long long                   
#define f first 
#define s second 
#define pb push_back               
#define mp make_pair 
#define IOS ios_base::sync_with_stdio(0);

using namespace std;                    

const ll maxn=2e5+123,inf=1e18,mod=1e9+7,N=360360,LOG=20;
vector<int>g[maxn];
int n,q,root,was[maxn],depth[maxn],mn[maxn],ord[maxn],cur,up[maxn][LOG];
set< pair<int,int> > st;
void dfs1(int v){
    for(int i=1;i<LOG;i++)
        up[v][i]=up[up[v][i-1]][i-1];
    mn[v]=v;
    for(auto to:g[v]){
        up[to][0]=v;
        depth[to]=depth[v]+1;
        dfs1(to);
        mn[v]=min(mn[v],mn[to]);
    }   
}
void dfs2(int v){
    ord[v]=--cur;
    st.insert({ord[v],v});
    vector< pair<int,int> >vec;
    for( auto to:g[v] )
        vec.pb({-mn[to],to});
    sort(vec.begin(),vec.end());
    for( auto to:vec )
        dfs2(to.s);
}
int main(){
    #ifdef LOCAL
        freopen ("test.in", "r", stdin);
    #endif                                     
    IOS
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        int p;
        cin>>p;
        g[p].pb(i);
        if(p==0)
            root=i;
    }
    dfs1(root);
    dfs2(root);
    while(q--){
        int type,x,y;
        cin>>type>>x;
        if(type==1){
            while(x--){
                int v=(*st.begin()).s;
                st.erase(st.begin());
                was[v]=1;
                y=v;
            }
            cout<<y<<endl;
        }else{
            y=x;
            for(int i=LOG-1;i>=0;i--)
                if( was[up[x][i]] )
                    x=up[x][i];
            was[x]=0;
            st.insert({ord[x],x});              
            cout<<depth[y]-depth[x]<<endl;
        }
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:66:19: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cout<<y<<endl;
                   ^

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 333 ms 15588 KB Output is correct
3 Correct 243 ms 15796 KB Output is correct
4 Correct 6 ms 15796 KB Output is correct
5 Correct 6 ms 15796 KB Output is correct
6 Correct 7 ms 15796 KB Output is correct
7 Correct 10 ms 15796 KB Output is correct
8 Correct 11 ms 15796 KB Output is correct
9 Correct 30 ms 15796 KB Output is correct
10 Correct 68 ms 15796 KB Output is correct
11 Correct 494 ms 16424 KB Output is correct
12 Correct 299 ms 16424 KB Output is correct
13 Correct 291 ms 16424 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 16424 KB Output is correct
2 Correct 439 ms 27560 KB Output is correct
3 Correct 262 ms 27560 KB Output is correct
4 Correct 253 ms 27560 KB Output is correct
5 Correct 226 ms 27560 KB Output is correct
6 Correct 239 ms 27560 KB Output is correct
7 Correct 325 ms 27560 KB Output is correct
8 Correct 191 ms 27560 KB Output is correct
9 Correct 552 ms 28728 KB Output is correct
10 Correct 507 ms 28728 KB Output is correct
11 Correct 446 ms 28728 KB Output is correct
12 Correct 434 ms 28728 KB Output is correct
13 Correct 363 ms 31604 KB Output is correct
14 Correct 387 ms 31604 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 269 ms 31604 KB Output is correct
2 Correct 580 ms 31604 KB Output is correct
3 Correct 368 ms 31604 KB Output is correct
4 Correct 322 ms 31604 KB Output is correct
5 Correct 371 ms 31604 KB Output is correct
6 Correct 285 ms 31604 KB Output is correct
7 Correct 269 ms 31604 KB Output is correct
8 Correct 291 ms 31604 KB Output is correct
9 Correct 647 ms 31604 KB Output is correct
10 Correct 627 ms 31604 KB Output is correct
11 Correct 460 ms 31604 KB Output is correct
12 Correct 454 ms 31604 KB Output is correct
13 Correct 537 ms 35444 KB Output is correct
14 Correct 434 ms 35444 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 470 ms 35444 KB Output is correct
2 Correct 594 ms 35444 KB Output is correct
3 Correct 368 ms 35444 KB Output is correct
4 Correct 419 ms 35444 KB Output is correct
5 Correct 491 ms 35444 KB Output is correct
6 Correct 430 ms 35444 KB Output is correct
7 Correct 489 ms 35444 KB Output is correct
8 Correct 362 ms 35444 KB Output is correct
9 Correct 330 ms 35444 KB Output is correct