제출 #667140

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
667140		ar_paixaos19	Ball Machine (BOI13_ballmachine)	C++17	92.30 / 100	1093 ms	30512 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100010;
const int LOGN = 20;

int t = 0;
int tin[MAXN], tout[MAXN], submin[MAXN], posicao[MAXN], pai[MAXN], dist[MAXN];
int marc[MAXN];
int up[LOGN+10][MAXN];
vector<int> grafo[MAXN];
set<int> s;

bool cmp(int i, int j){
    return submin[i] < submin[j];
}


void dfs(int v, int p, int id){

    submin[v] = v;
    for(auto viz : grafo[v]){
        if(viz == p) continue;
        dist[viz] = dist[v] + 1;
        dfs(viz, v, id);
        submin[v] = min(submin[v], submin[viz]);
    }

    if(id == 1){
        tout[v] = ++t;
        posicao[t] = v;
        return;
    }
    for(int i = 0; i < grafo[v].size(); i++){
        sort(grafo[v].begin(), grafo[v].end(), cmp);
    }

    return;
}

void calcup(int n){
    for(int i = 1; i <= n; i++){
        up[0][i] = pai[i];
    }

    for(int k = 1; k < LOGN; k++){
        for(int i = 1; i <= n; i++){
            up[k][i] = up[k - 1][ up[k - 1][i] ];
        }
    }

    return;
}

int bsbl(int v, int n){
    for(int k = LOGN - 1; k >= 0; k--){
        if(marc[ tout[ up[k][v] ] ] == 1){
            //printf("deu no k = %d\n", k);
            v = up[k][v];
        }
    }

    return v;
}

template<typename T> void read(T& aa)
{
	aa=0;
	char cc=getchar();
	T ff=1;

	while((cc != '-') && (cc < '0' || cc > '9')) cc=getchar();

	if(cc=='-') ff=-1, cc=getchar();

	while(cc >= '0' && cc <= '9') aa = aa*10 + cc - '0', cc=getchar();
	aa*=ff;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, q; read(n), read(q);
    int root;
    for(int i = 1; i <= n; i++){
        int v; read(v);
        if(v == 0){
            root = i;
            pai[root] = root;
            continue;
        }

        pai[i] = v;
        grafo[i].push_back(v);
        grafo[v].push_back(i);
    }

    dfs(root, root, 0);
    dfs(root, root, 1);
    calcup(n);
    for(int i = 1; i <= n; i++){
        s.insert(tout[i]);
    }

    for(int i = 1; i <= q; i++){
        int type; read(type);

        if(type == 1){
            int k; read(k);

            int b;
            for(int j = 1; j <= k; j++){
                b = *s.begin();
                marc[b] = 1;
                s.erase(s.begin());
            }

            cout << posicao[b] << '\n';
        }
        if(type == 2){
            int x; read(x);

            int r = bsbl(x, n);
            cout <<  dist[x] - dist[r] << '\n';
            marc[ tout[r] ] = 0;
            s.insert(tout[r]);
        }
    }

    /*for(int i = 1; i <= n; i++){
        printf("up[%d]:\n", i);
        for(int k = 0; k < LOGN; k++){
            printf("\tup[%d][%d] = %d\n", k, i, up[k][i]);
        }
    }*/


    /*for(int i = 1; i <= q; i++){
        int type; scanf("%d", &type);
        if(type == 1){
            int l, r, val; scanf("%d %d %d", &l, &r, &val);
            update(1, 1, n, l, r, val);
        }
        if(type == 2){
            int s; scanf("%d", &s);
            printf("%d\n", bs(1, 1, n, s));
        }

    }*/


    return 0;
}

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

ballmachine.cpp: In function 'void dfs(int, int, int)':
ballmachine.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i = 0; i < grafo[v].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:117:35: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
  117 |             cout << posicao[b] << '\n';
      |                                   ^~~~
ballmachine.cpp:98:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |     dfs(root, root, 1);
      |     ~~~^~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 25.714285714285715 / 30
• Subtask 3: 37.142857142857146 / 40
• Subtask 4: 4.444444444444445 / 5