oj.uz

Submission #30859

# Submission time Handle Problem Language Result Execution time Memory
30859 2017-07-28T14:36:19 Z Navick Ball Machine (BOI13_ballmachine) C++14
11.5385 / 100
 253 ms 28308 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10 , LG = 20;
int par[LG][N] , h[N] , st[N] , tim = 0 , root = -1 , f[N] , en[N] , mini[N];
bool used[N];
vector<int > child[N];
set<pair<int,int> > s;

bool cmp(int a,int b){
    return mini[a] < mini[b];
}

void p_dfs(int v,int p=0){
    mini[v] = v;
    for(auto u:child[v]){
        if(u == p)continue;
        p_dfs(u , v);
        mini[v] = min(mini[v] , mini[u]);
    }
}


void dfs(int v , int p = 0){

    par[0][v] = p;
    for(int i=1;i<LG;i++)par[i][v] = par[i-1][par[i-1][v]];

    st[v] = tim++;
    for(auto u:child[v]){
        h[u] = h[v] + 1;
        dfs(u , v);
    }
    en[v] = tim;
}


int i_par(int v,int x){
    for(int i = LG - 1; i>=0 ; i--){
        if(x & (1<<i))v = par[i][v];
    }
    return v;
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    int n , q; cin>>n>>q;
    for(int i=1;i<=n;i++){
        int p; cin>>p;
        if(p == 0)root = i;
        else child[p].push_back(i);
    }

    p_dfs(root);

    for(int i=1;i<=n;i++)sort(child[i].begin() , child[i].end() , cmp);

    dfs(root);

    for(int i=1;i<=n;i++)s.insert({en[i] , -st[i]});

    for(int i=1;i<=n;i++)f[st[i]] = i;

    while(q--){
        int type; cin>>type;
        if(type == 1){
            int k , ind ; cin>>k;
            while(k--){
                ind = (*s.begin()).second; ind = -ind;
                s.erase(s.begin());
                used[ind] = true;
            }
            cout<<f[ind]<<'\n';
        }else{
            int v; cin>>v;
            int lo = 0 , hi = h[v] + 1;
            while(hi - lo > 1){
                int mid = (lo + hi)/2;
                int p = i_par(v , mid);
                if(used[st[p]] == true)lo = mid; else hi = mid;
            }
            int x = i_par(v , lo);
            used[st[x]] = false;
            cout<<h[v] - h[x]<<'\n';
            s.insert({en[x] , -st[x]});
        }
    }
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:72:24: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
             cout<<f[ind]<<'\n';
                        ^

Subtask #1
11.5384615385 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 14392 KB Output is correct
2 Runtime error 103 ms 18484 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 86 ms 18484 KB Execution killed because of forbidden syscall writev (20)
4 Correct 0 ms 14392 KB Output is correct
5 Correct 0 ms 14392 KB Output is correct
6 Correct 0 ms 14392 KB Output is correct
7 Correct 3 ms 14392 KB Output is correct
8 Correct 3 ms 14392 KB Output is correct
9 Runtime error 3 ms 14656 KB Execution killed because of forbidden syscall writev (20)
10 Runtime error 16 ms 15448 KB Execution killed because of forbidden syscall writev (20)
11 Runtime error 99 ms 18484 KB Execution killed because of forbidden syscall writev (20)
12 Runtime error 49 ms 18484 KB Execution killed because of forbidden syscall writev (20)
13 Runtime error 93 ms 18484 KB Execution killed because of forbidden syscall writev (20)

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 ms 16856 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 243 ms 23988 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 136 ms 20460 KB Execution killed because of forbidden syscall writev (20)
4 Runtime error 19 ms 17320 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 49 ms 17180 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 46 ms 17180 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 49 ms 16548 KB Execution killed because of forbidden syscall writev (20)
8 Runtime error 16 ms 16864 KB Execution killed because of forbidden syscall writev (20)
9 Runtime error 213 ms 24384 KB Execution killed because of forbidden syscall writev (20)
10 Runtime error 253 ms 23988 KB Execution killed because of forbidden syscall writev (20)
11 Runtime error 123 ms 23992 KB Execution killed because of forbidden syscall writev (20)
12 Runtime error 116 ms 22260 KB Execution killed because of forbidden syscall writev (20)
13 Runtime error 156 ms 26644 KB Execution killed because of forbidden syscall writev (20)
14 Runtime error 136 ms 20460 KB Execution killed because of forbidden syscall writev (20)

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 83 ms 19264 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 243 ms 22428 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 96 ms 25472 KB Execution killed because of forbidden syscall writev (20)
4 Runtime error 83 ms 22440 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 76 ms 22048 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 76 ms 22044 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 79 ms 20792 KB Execution killed because of forbidden syscall writev (20)
8 Runtime error 86 ms 25468 KB Execution killed because of forbidden syscall writev (20)
9 Runtime error 109 ms 24388 KB Execution killed because of forbidden syscall writev (20)
10 Runtime error 123 ms 23996 KB Execution killed because of forbidden syscall writev (20)
11 Runtime error 126 ms 23988 KB Execution killed because of forbidden syscall writev (20)
12 Runtime error 119 ms 22428 KB Execution killed because of forbidden syscall writev (20)
13 Runtime error 119 ms 28308 KB Execution killed because of forbidden syscall writev (20)
14 Runtime error 136 ms 20460 KB Execution killed because of forbidden syscall writev (20)

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 206 ms 24388 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 233 ms 22432 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 146 ms 28300 KB Execution killed because of forbidden syscall writev (20)
4 Runtime error 219 ms 24384 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 233 ms 23996 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 239 ms 23992 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 219 ms 22428 KB Execution killed because of forbidden syscall writev (20)
8 Runtime error 196 ms 28308 KB Execution killed because of forbidden syscall writev (20)
9 Runtime error 116 ms 20460 KB Execution killed because of forbidden syscall writev (20)