제출 #337317

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
337317		Giselus	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	267 ms	34924 KiB

ballmachine

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5