oj.uz

Submission #25835

# Submission time Handle Problem Language Result Execution time Memory
25835 2017-06-24T09:40:44 Z gs14004 Ball Machine (BOI13_ballmachine) C++11
100 / 100
 803 ms 24080 KB 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
  
int n, q;
  
int dfn[100005], rev[100005];
int par[100005][17];
int dep[100005];
vector<int> graph[100005];
  
int piv;
int root;
 
int min_sub[100005];
 
int prep(int x){
    min_sub[x] = x;
    for(int ii=0; ii<graph[x].size(); ii++){
        int i = graph[x][ii];
        min_sub[x] = min(min_sub[x],prep(i));
    }
    return min_sub[x];
}
 
bool cmp(int a, int b){
    return min_sub[a] < min_sub[b];
}
 
void dfs(int x){
    for(int i=1; i<17; i++){
        par[x][i] = par[par[x][i-1]][i-1];
    }
    for(int ii=0; ii<graph[x].size(); ii++){
        int i = graph[x][ii];
        dep[i] = dep[x] + 1;
        dfs(i);
    }
    dfn[x] = ++piv;
    rev[dfn[x]] = x;
}
 
set<int> s;
 
int main(){
    scanf("%d %d",&n,&q);
    for(int i=1; i<=n; i++){
        s.insert(i);
        scanf("%d",&par[i][0]);
        if(par[i][0]) graph[par[i][0]].push_back(i);
        else root = i;
    }
    prep(root);
    for(int i=1; i<=n; i++){
        sort(graph[i].begin(), graph[i].end(),cmp);
    }
    dfs(root);
    while(q--){
        int a, b;
        scanf("%d %d",&a,&b);
        if(a == 1){
            int p;
            while(b--) p = *s.begin(), s.erase(s.begin());
            printf("%d\n",rev[p]);
        }
        else{
            int op = dep[b];
            for(int i=16; i>=0; i--){
                if(par[b][i] == 0) continue;
                if(s.find(dfn[par[b][i]]) == s.end()){
                    b = par[b][i];
                }
            }
            s.insert(dfn[b]);
            printf("%d\n",op - dep[b]);
        }
    }
}

Compilation message

ballmachine.cpp: In function 'int prep(int)':
ballmachine.cpp:21:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int ii=0; ii<graph[x].size(); ii++){
                     ^
ballmachine.cpp: In function 'void dfs(int)':
ballmachine.cpp:36:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int ii=0; ii<graph[x].size(); ii++){
                     ^
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:48:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&q);
                         ^
ballmachine.cpp:51:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&par[i][0]);
                               ^
ballmachine.cpp:62:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&a,&b);
                             ^
ballmachine.cpp:66:19: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
             printf("%d\n",rev[p]);
                   ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11728 KB Output is correct
2 Correct 286 ms 15820 KB Output is correct
3 Correct 129 ms 15820 KB Output is correct
4 Correct 0 ms 11728 KB Output is correct
5 Correct 3 ms 11728 KB Output is correct
6 Correct 0 ms 11860 KB Output is correct
7 Correct 3 ms 11860 KB Output is correct
8 Correct 3 ms 11860 KB Output is correct
9 Correct 13 ms 11992 KB Output is correct
10 Correct 43 ms 12784 KB Output is correct
11 Correct 263 ms 15820 KB Output is correct
12 Correct 76 ms 15820 KB Output is correct
13 Correct 159 ms 15820 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 13912 KB Output is correct
2 Correct 639 ms 20540 KB Output is correct
3 Correct 153 ms 17812 KB Output is correct
4 Correct 233 ms 14416 KB Output is correct
5 Correct 283 ms 14284 KB Output is correct
6 Correct 236 ms 14280 KB Output is correct
7 Correct 229 ms 13772 KB Output is correct
8 Correct 63 ms 13912 KB Output is correct
9 Correct 396 ms 21076 KB Output is correct
10 Correct 613 ms 20544 KB Output is correct
11 Correct 446 ms 20544 KB Output is correct
12 Correct 533 ms 19216 KB Output is correct
13 Correct 229 ms 22600 KB Output is correct
14 Correct 156 ms 17812 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 16336 KB Output is correct
2 Correct 713 ms 19372 KB Output is correct
3 Correct 389 ms 21560 KB Output is correct
4 Correct 276 ms 19156 KB Output is correct
5 Correct 476 ms 18760 KB Output is correct
6 Correct 483 ms 18760 KB Output is correct
7 Correct 486 ms 17820 KB Output is correct
8 Correct 429 ms 21556 KB Output is correct
9 Correct 519 ms 21080 KB Output is correct
10 Correct 783 ms 20548 KB Output is correct
11 Correct 656 ms 20548 KB Output is correct
12 Correct 756 ms 19376 KB Output is correct
13 Correct 686 ms 24076 KB Output is correct
14 Correct 273 ms 17928 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 21080 KB Output is correct
2 Correct 626 ms 19376 KB Output is correct
3 Correct 313 ms 24080 KB Output is correct
4 Correct 499 ms 21072 KB Output is correct
5 Correct 803 ms 20548 KB Output is correct
6 Correct 489 ms 20548 KB Output is correct
7 Correct 736 ms 19376 KB Output is correct
8 Correct 276 ms 24080 KB Output is correct
9 Correct 159 ms 17928 KB Output is correct