oj.uz

Submission #58558

# Submission time Handle Problem Language Result Execution time Memory
58558 2018-07-18T07:35:57 Z Batrr Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 1000 ms 78252 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                                     
    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:65:19: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cout<<y<<endl;
                   ^

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 5240 KB Time limit exceeded
2 Execution timed out 1079 ms 16884 KB Time limit exceeded
3 Incorrect 328 ms 18160 KB Output isn't correct
4 Execution timed out 1073 ms 18160 KB Time limit exceeded
5 Execution timed out 1077 ms 18160 KB Time limit exceeded
6 Incorrect 10 ms 18160 KB Output isn't correct
7 Execution timed out 1076 ms 18160 KB Time limit exceeded
8 Execution timed out 1081 ms 18160 KB Time limit exceeded
9 Execution timed out 1072 ms 18160 KB Time limit exceeded
10 Execution timed out 1088 ms 18160 KB Time limit exceeded
11 Execution timed out 1081 ms 19140 KB Time limit exceeded
12 Incorrect 337 ms 20512 KB Output isn't correct
13 Execution timed out 1042 ms 21476 KB Time limit exceeded

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 21476 KB Output is correct
2 Incorrect 659 ms 33948 KB Output isn't correct
3 Incorrect 353 ms 33948 KB Output isn't correct
4 Execution timed out 1073 ms 33948 KB Time limit exceeded
5 Execution timed out 1075 ms 33948 KB Time limit exceeded
6 Incorrect 367 ms 33948 KB Output isn't correct
7 Execution timed out 1076 ms 33948 KB Time limit exceeded
8 Correct 246 ms 33948 KB Output is correct
9 Execution timed out 1085 ms 39760 KB Time limit exceeded
10 Incorrect 642 ms 40272 KB Output isn't correct
11 Incorrect 529 ms 41616 KB Output isn't correct
12 Execution timed out 1088 ms 41616 KB Time limit exceeded
13 Correct 444 ms 47828 KB Output is correct
14 Incorrect 330 ms 47828 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 353 ms 47828 KB Output isn't correct
2 Incorrect 785 ms 47828 KB Output isn't correct
3 Correct 423 ms 49676 KB Output is correct
4 Incorrect 448 ms 49676 KB Output isn't correct
5 Incorrect 430 ms 49676 KB Output isn't correct
6 Incorrect 401 ms 49676 KB Output isn't correct
7 Incorrect 407 ms 49676 KB Output isn't correct
8 Correct 373 ms 54324 KB Output is correct
9 Incorrect 547 ms 55172 KB Output isn't correct
10 Incorrect 535 ms 55436 KB Output isn't correct
11 Incorrect 531 ms 56692 KB Output isn't correct
12 Incorrect 578 ms 56692 KB Output isn't correct
13 Correct 536 ms 67028 KB Output is correct
14 Incorrect 629 ms 67028 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 67028 KB Time limit exceeded
2 Incorrect 702 ms 67028 KB Output isn't correct
3 Correct 602 ms 71636 KB Output is correct
4 Execution timed out 1089 ms 71636 KB Time limit exceeded
5 Incorrect 655 ms 71636 KB Output isn't correct
6 Incorrect 488 ms 71636 KB Output isn't correct
7 Incorrect 660 ms 71636 KB Output isn't correct
8 Correct 509 ms 78252 KB Output is correct
9 Incorrect 391 ms 78252 KB Output isn't correct