Submission #242122

#	Time	Username	Problem	Language	Result	Execution time	Memory
242122		pauloamed	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	462 ms	20856 KiB

ballmachine

#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 (stderr)

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