oj.uz

Submission #337317

# Submission time Handle Problem Language Result Execution time Memory
337317 2020-12-19T16:54:14 Z Giselus Ball Machine (BOI13_ballmachine) C++14
100 / 100
 267 ms 34924 KB 
#include<cstdio>
#include<algorithm>
#include<vector>
#define S 131072
 
using namespace std;
 
int tree[2*S+7];
 
vector < vector < int > > L;
vector < vector < pair < int , int > > > L2;
 
int dp[S];
int R[S][20];
int pod[S];
int kol[S];
int kol2[S];
int poz[S];
bool zab[S];
 
void DFS(int x){
    dp[x] = x;
    pod[x] = 1;
    for(int i = 1; i <= 19;i++){
        R[x][i] = R[R[x][i-1]][i-1];
    }
    for(int i = 0;i < L[x].size();i++){
        R[L[x][i]][0] = x;
        poz[L[x][i]] = poz[x] + 1;
        DFS(L[x][i]);
        pod[x] += pod[L[x][i]];
        dp[x] = min(dp[x],dp[L[x][i]]);
        L2[x].push_back({dp[L[x][i]],L[x][i]});
 
    }
}
 
int p = 0;
void DFS2(int x){
    for(int i = 0 ; i < L2[x].size();i++){
        DFS2(L2[x][i].second);
    }
    p++;
    kol[x] = p;
    kol2[p] = x;
}
 
int main(void){
int n,m,a,b,c,d,x,k,q;
scanf("%d %d",&n,&q);
L.resize(n+8);
L2.resize(n+8);
int root;
for(int i = 1; i<= n;i++){
    scanf("%d",&x);
    if(x == 0)
        root = i;
    else
        L[x].push_back(i);
}
R[root][0] = root;
DFS(root);
for(int i = 1; i <= n;i++){
    tree[i+S-1] = 1;
    sort(L2[i].begin(),L2[i].end());
}
for(int i = S-1;i >= 1;i--)
    tree[i] = tree[i*2] + tree[i*2+1];
DFS2(root);
 
 
 
for(int i = 1; i <= q;i++){
    scanf("%d %d",&a,&b);
    if(a == 1){
        for(int j = 1; j <= b;j++){
            int w = 1;
            while(w < S){
                if(tree[w*2] >= 1){
                    w *= 2;
                }else{
                    w = w*2+1;
                }
            }
            if(j == b)
                printf("%d\n",kol2[w-S+1]);
            zab[kol2[w-S+1]] = 1;
            while(w != 0){
                tree[w]--;
                w/=2;
            }
 
        }
    }else{
        c = b;
        for(int i = 19;i>=0;i--){
            if(zab[R[b][i]])
                b = R[b][i];
        }
        printf("%d\n",poz[c] - poz[b]);
        zab[b] = 0;
        b = kol[b];
        b = b + S -1;
        while(b != 0){
            tree[b]++;
            b/=2;
        }
    }
}
 
return 0;
}

Compilation message

ballmachine.cpp: In function 'void DFS(int)':
ballmachine.cpp:27:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i = 0;i < L[x].size();i++){
      |                   ~~^~~~~~~~~~~~~
ballmachine.cpp: In function 'void DFS2(int)':
ballmachine.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i = 0 ; i < L2[x].size();i++){
      |                     ~~^~~~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:49:7: warning: unused variable 'm' [-Wunused-variable]
   49 | int n,m,a,b,c,d,x,k,q;
      |       ^
ballmachine.cpp:49:15: warning: unused variable 'd' [-Wunused-variable]
   49 | int n,m,a,b,c,d,x,k,q;
      |               ^
ballmachine.cpp:49:19: warning: unused variable 'k' [-Wunused-variable]
   49 | int n,m,a,b,c,d,x,k,q;
      |                   ^
ballmachine.cpp:50:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 | scanf("%d %d",&n,&q);
      | ~~~~~^~~~~~~~~~~~~~~
ballmachine.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |     scanf("%d",&x);
      |     ~~~~~^~~~~~~~~
ballmachine.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |     scanf("%d %d",&a,&b);
      |     ~~~~~^~~~~~~~~~~~~~~
ballmachine.cpp:69:5: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 | DFS2(root);
      | ~~~~^~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 876 KB Output is correct
2 Correct 143 ms 14060 KB Output is correct
3 Correct 95 ms 14060 KB Output is correct
4 Correct 1 ms 876 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 2 ms 1004 KB Output is correct
7 Correct 2 ms 1004 KB Output is correct
8 Correct 2 ms 1004 KB Output is correct
9 Correct 10 ms 1644 KB Output is correct
10 Correct 29 ms 4076 KB Output is correct
11 Correct 139 ms 14040 KB Output is correct
12 Correct 100 ms 14076 KB Output is correct
13 Correct 133 ms 14056 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 7532 KB Output is correct
2 Correct 219 ms 26824 KB Output is correct
3 Correct 122 ms 19812 KB Output is correct
4 Correct 89 ms 9428 KB Output is correct
5 Correct 94 ms 9324 KB Output is correct
6 Correct 103 ms 9116 KB Output is correct
7 Correct 83 ms 7808 KB Output is correct
8 Correct 50 ms 7532 KB Output is correct
9 Correct 200 ms 27756 KB Output is correct
10 Correct 223 ms 26992 KB Output is correct
11 Correct 212 ms 26876 KB Output is correct
12 Correct 212 ms 23832 KB Output is correct
13 Correct 169 ms 30700 KB Output is correct
14 Correct 117 ms 19788 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 14432 KB Output is correct
2 Correct 238 ms 24400 KB Output is correct
3 Correct 193 ms 27884 KB Output is correct
4 Correct 147 ms 22252 KB Output is correct
5 Correct 174 ms 21612 KB Output is correct
6 Correct 175 ms 21600 KB Output is correct
7 Correct 161 ms 19356 KB Output is correct
8 Correct 179 ms 27884 KB Output is correct
9 Correct 222 ms 27892 KB Output is correct
10 Correct 267 ms 27164 KB Output is correct
11 Correct 241 ms 27116 KB Output is correct
12 Correct 240 ms 24228 KB Output is correct
13 Correct 255 ms 34924 KB Output is correct
14 Correct 156 ms 20324 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 28012 KB Output is correct
2 Correct 230 ms 24300 KB Output is correct
3 Correct 191 ms 34540 KB Output is correct
4 Correct 227 ms 28012 KB Output is correct
5 Correct 235 ms 27116 KB Output is correct
6 Correct 212 ms 27024 KB Output is correct
7 Correct 226 ms 24280 KB Output is correct
8 Correct 194 ms 34552 KB Output is correct
9 Correct 112 ms 19924 KB Output is correct