oj.uz

Submission #242122

# Submission time Handle Problem Language Result Execution time Memory
242122 2020-06-26T22:17:54 Z pauloamed Ball Machine (BOI13_ballmachine) C++14
100 / 100
 462 ms 20856 KB 
#include<bits/stdc++.h>
using namespace std;

#define MAXV 110000
#define MAXLOG 17

vector<int> v[MAXV]; // lista de adj

int st[MAXV][MAXLOG]; // sparse table (x,i) guardando ancestral de ordem 2^i de x
int lvl[MAXV]; // lvl=profundidade de cada no
int bit[MAXV];
int pos_id[MAXV];
int id_pos[MAXV];
int pos_cont = 0;
bool active[MAXV];

int query( int index ){
    if(index < 0 || index > MAXV) return 0;
    int ans(0); // acumulado
    index++; // bit eh 1-indexada, tem q ser feito se index for 0-indexado
    while(index > 0){ // enquanto posso ir pra esquerda
        ans += bit[index]; // atualizando o acumulado
        index -= index & (-index); // indo pro irmao a esquerda
    }
    return ans; // ret acumulado
}


void update(int index, int val){
    if(index < 0 || index > MAXV) return;
    index++; // bit eh 1-indexada
    while(index <= MAXV){ // enquanto eu puder subir na BIT
        bit[index] += val; // atualizando valores dos ancestrais
        index += index & (-index); // subindo pro pai
    }
}


void init_dfs(int x, int pai, bool jafoi[]){
    jafoi[x] = true; // marcando vertice como visitado
    st[x][0] = pai; // o ancestral de ordem 2^0 (1) de x eh o pai dele
    // se tiver pai valido (!= raiz), a prof aumenta em 1
    if(pai != -1) lvl[x] = lvl[pai]+1;
    for(int i = 0; i < v[x].size(); ++i) // visitar todos adjacentes
        if(!jafoi[v[x][i]]) init_dfs(v[x][i], x, jafoi); // passo recursivo

    pos_id[pos_cont] = x;
    id_pos[x] = pos_cont;
    pos_cont++;
}


void init(int root, int n){ // funcao init, raiz e #nos
    bool *jafoi = new bool[n]; // visitados
    init_dfs(root, root, jafoi); // calcular os ancestrais imediatos
    delete[] jafoi;
    for(int x = 1; x < MAXLOG; ++x){
        // 2^0 ja foi calculado, calculo pro resto
        for(int i = 0; i < MAXV; ++i){ // pra cada vertice
            if(i == root){
                st[i][x] = root;
            }else{
                // olho o ancestral 2^(i-1) do meu 2^(i-1), achando entao o meu 2^i
                st[i][x] = st[st[i][x-1]][x-1];
            }
        }
    }
}



int smallest[MAXV];
bool cmp(const int a, const int b){
    return smallest[a] < smallest[b];
}
void find_smallest(int x){
    smallest[x] = x;
    for(int i = 0; i < v[x].size(); ++i){
        find_smallest(v[x][i]);
        smallest[x] = min(smallest[x], smallest[v[x][i]]);
    }
}


int first_zero(){
    int ans = 0;
    if(bit[1] == 0) return 0;
    for(int i = MAXLOG-1; i >= 0; --i){
        int maybe_ans = (ans | (1<<i)); // novo indice se o bit for ativo
        if(maybe_ans >= MAXV) continue; // caso ultrapasse o limite no calc do indice
        // printf("%d %d %d\n", maybe_ans, bit[maybe_ans], (1<<i));
        if(bit[maybe_ans] == (1 << i)) ans = maybe_ans;
    }
    // cout << ans << endl;
    return ans;
}


int add(int k){
    // procura na bit o primeiro zero
    // bota o primeiro zero la
    // retorn a posicao
    int ans;
    while(k--){
        ans = first_zero();
        update(ans, 1);
        active[ans] = true;
    }
    return ans;
}

int remove(int x){
    // acha o ultimo pai q eh 1
    // se nao tem, retorna X
    // se tem, tira ele da bit e bota em X
    int curr = x;
    // cerr << "::" << x << endl;
    for(int i = MAXLOG-1; i >= 0; --i){
        int maybe_next = st[curr][i];
        int pos_maybe_next = id_pos[maybe_next];
        if(active[pos_maybe_next]){
            curr = maybe_next;
        }
    }

    // cerr << "::" << curr << " " << x << endl;
    // cerr << "::" << id_pos[curr] << " " << id_pos[x] << endl;

    update(id_pos[curr], -1);
    active[id_pos[curr]] = false;

    return lvl[x] - lvl[curr];
}


int main(){
    // add: achar a primeira posicao que é zero
    // remove: subir com binary lifting ate o pai ta ocupado
    int n, q; cin >> n >> q;
    int root;
    for(int i = 0; i < n; ++i){
        int x; cin >> x;
        if(x == 0) root = i;
        else v[x-1].push_back(i);
    }

    find_smallest(root);
    for(int i = 0; i < n; ++i){
        sort(v[i].begin(), v[i].end(), cmp);
    }

    init(root, n);

    // for(int i = 0; i < n; ++i){
    //     printf("%d ", id_pos[i]);
    // }printf("\n");

    while(q--){
        // for(int i = 0; i < n; ++i){
        //     printf("(%d) %d: %d\n", i, pos_id[i] + 1, query(i) - query(i - 1));
        // }
        // printf("\n");
        int x; cin >> x;
        if(x == 1){
            int k; cin >> k;
            cout << pos_id[add(k)] + 1 << endl;
        }else{
            int y; cin >> y;
            cout << remove(y - 1) << endl;
        }
    }
}

Compilation message

ballmachine.cpp: In function 'void init_dfs(int, int, bool*)':
ballmachine.cpp:44:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[x].size(); ++i) // visitar todos adjacentes
                    ~~^~~~~~~~~~~~~
ballmachine.cpp: In function 'void find_smallest(int)':
ballmachine.cpp:78:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[x].size(); ++i){
                    ~~^~~~~~~~~~~~~
ballmachine.cpp: In function 'int add(int)':
ballmachine.cpp:109:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ans;
            ^~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:152:9: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
     init(root, n);
     ~~~~^~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 10240 KB Output is correct
2 Correct 378 ms 13052 KB Output is correct
3 Correct 325 ms 12760 KB Output is correct
4 Correct 21 ms 10240 KB Output is correct
5 Correct 17 ms 10368 KB Output is correct
6 Correct 18 ms 10368 KB Output is correct
7 Correct 21 ms 10240 KB Output is correct
8 Correct 20 ms 10240 KB Output is correct
9 Correct 42 ms 10368 KB Output is correct
10 Correct 91 ms 10876 KB Output is correct
11 Correct 373 ms 13040 KB Output is correct
12 Correct 319 ms 12796 KB Output is correct
13 Correct 355 ms 12628 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 12280 KB Output is correct
2 Correct 458 ms 16760 KB Output is correct
3 Correct 327 ms 13524 KB Output is correct
4 Correct 282 ms 12532 KB Output is correct
5 Correct 282 ms 12408 KB Output is correct
6 Correct 273 ms 12152 KB Output is correct
7 Correct 275 ms 11768 KB Output is correct
8 Correct 242 ms 12280 KB Output is correct
9 Correct 416 ms 17144 KB Output is correct
10 Correct 416 ms 16944 KB Output is correct
11 Correct 401 ms 16504 KB Output is correct
12 Correct 415 ms 15416 KB Output is correct
13 Correct 365 ms 19064 KB Output is correct
14 Correct 334 ms 13556 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 13944 KB Output is correct
2 Correct 447 ms 16120 KB Output is correct
3 Correct 295 ms 18568 KB Output is correct
4 Correct 283 ms 15864 KB Output is correct
5 Correct 269 ms 15480 KB Output is correct
6 Correct 277 ms 15480 KB Output is correct
7 Correct 278 ms 14588 KB Output is correct
8 Correct 294 ms 18552 KB Output is correct
9 Correct 423 ms 17532 KB Output is correct
10 Correct 462 ms 17144 KB Output is correct
11 Correct 426 ms 17016 KB Output is correct
12 Correct 445 ms 15864 KB Output is correct
13 Correct 462 ms 20856 KB Output is correct
14 Correct 402 ms 13940 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 17480 KB Output is correct
2 Correct 443 ms 15736 KB Output is correct
3 Correct 374 ms 20216 KB Output is correct
4 Correct 419 ms 17400 KB Output is correct
5 Correct 442 ms 16904 KB Output is correct
6 Correct 424 ms 16676 KB Output is correct
7 Correct 425 ms 15864 KB Output is correct
8 Correct 379 ms 20228 KB Output is correct
9 Correct 321 ms 13556 KB Output is correct