oj.uz

Submission #153586

# Submission time Handle Problem Language Result Execution time Memory
153586 2019-09-14T18:27:42 Z brcode Ball Machine (BOI13_ballmachine) C++14
100 / 100
 696 ms 28092 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int n,q;
int root;
const int MAXN = 1e5+5;
const int MAXK = 25;
vector<int> v1[MAXN];
int par[MAXN][MAXK];
int subtreemin[MAXN];

int currtime = 1;
bool occupied[MAXN];
int timer[MAXN];
int depth[MAXN];
bool cmp(int x,int y){
    return subtreemin[x]<subtreemin[y];
}
bool cmp2(int x,int y){
    return timer[x]<timer[y];
}
set<int,decltype(&cmp2)> s1(&cmp2);
void dfs(int curr){
    subtreemin[curr] = curr;
    for(int x:v1[curr]){
        depth[x] = depth[curr]+1;
        dfs(x);
        subtreemin[curr] = min(subtreemin[curr],subtreemin[x]);
    }
}
void dfs2(int curr){

    for(int x:v1[curr]){
        dfs2(x);
    }
    timer[curr] = currtime++;
    //cout<<curr<<" "<<timer[curr]<<endl;
    s1.insert(curr);
}
int addball(){
    int ans = *s1.begin();
    s1.erase(s1.begin());
    occupied[ans] = true;
    return ans;
}
int removeball(int x){
    int original = x;
    for(int i=19;i>=0;i--){
        if(par[x][i]!=-1 && occupied[par[x][i]]){
            x=par[x][i];
        }

    }
    occupied[x] = false;
    s1.insert(x);
    return depth[original]-depth[x];
}
int main(){
   cin>>n>>q;
   for(int i=1;i<=n;i++){
        int p;
        cin>>p;
        if(p==0){
            root = i;
            par[i][0] = -1;
            continue;
        }
        par[i][0] = p;
        v1[p].push_back(i);
   }
   depth[root] = 0;
   for(int i=1;i<=n;i++){
        subtreemin[i] = MAXN;

   }

   dfs(root);
   for(int i=1;i<=n;i++){
        sort(v1[i].begin(),v1[i].end(),cmp);
   }
   dfs2(root);
   for(int i=1;i<MAXK;i++){
        for(int j=1;j<=n;j++){
            if(par[j][i-1] == -1){
                par[j][i] = -1;
            }else{
                par[j][i] = par[par[j][i-1]][i-1];
            }
        }
   }
   for(int i=1;i<=q;i++){
        int t;
        cin>>t;
        if(t==1){
            int val;
            cin>>val;
            int x;
            for(int j=1;j<=val;j++){
                x = addball();
             //   cout<<123<<" "<<x<<endl;
            }
            cout<<x<<endl;
        }else{
            int val;
            cin>>val;
            cout<<removeball(val)<<endl;
        }
   }
}

Compilation message

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

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 552 ms 15476 KB Output is correct
3 Correct 456 ms 15428 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 5 ms 2680 KB Output is correct
6 Correct 7 ms 2808 KB Output is correct
7 Correct 9 ms 2808 KB Output is correct
8 Correct 10 ms 2936 KB Output is correct
9 Correct 39 ms 3576 KB Output is correct
10 Correct 114 ms 5844 KB Output is correct
11 Correct 568 ms 15736 KB Output is correct
12 Correct 448 ms 15540 KB Output is correct
13 Correct 526 ms 15660 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 7888 KB Output is correct
2 Correct 649 ms 24260 KB Output is correct
3 Correct 477 ms 20980 KB Output is correct
4 Correct 383 ms 9720 KB Output is correct
5 Correct 396 ms 9720 KB Output is correct
6 Correct 385 ms 9712 KB Output is correct
7 Correct 395 ms 8848 KB Output is correct
8 Correct 315 ms 7928 KB Output is correct
9 Correct 665 ms 24736 KB Output is correct
10 Correct 659 ms 24272 KB Output is correct
11 Correct 594 ms 24404 KB Output is correct
12 Correct 643 ms 23052 KB Output is correct
13 Correct 520 ms 24872 KB Output is correct
14 Correct 470 ms 20780 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 13820 KB Output is correct
2 Correct 668 ms 23332 KB Output is correct
3 Correct 423 ms 22940 KB Output is correct
4 Correct 413 ms 20352 KB Output is correct
5 Correct 409 ms 19960 KB Output is correct
6 Correct 423 ms 20036 KB Output is correct
7 Correct 427 ms 18980 KB Output is correct
8 Correct 411 ms 22864 KB Output is correct
9 Correct 654 ms 25080 KB Output is correct
10 Correct 659 ms 24596 KB Output is correct
11 Correct 671 ms 24524 KB Output is correct
12 Correct 696 ms 23588 KB Output is correct
13 Correct 652 ms 28092 KB Output is correct
14 Correct 639 ms 21420 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 640 ms 25184 KB Output is correct
2 Correct 662 ms 23336 KB Output is correct
3 Correct 523 ms 27872 KB Output is correct
4 Correct 637 ms 25012 KB Output is correct
5 Correct 657 ms 24356 KB Output is correct
6 Correct 596 ms 24412 KB Output is correct
7 Correct 658 ms 23216 KB Output is correct
8 Correct 510 ms 27740 KB Output is correct
9 Correct 488 ms 20860 KB Output is correct