Submission #242120

#	Time	Username	Problem	Language	Result	Execution time	Memory
242120		pauloamed	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	585 ms	23928 KiB

ballmachine

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

#define MAXV 110000
#define MAXLOG 23

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;

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 add(int k){
    // procura na bit o primeiro zero
    // bota o primeiro zero la
    // retorn a posicao
    int ans;
    while(k--){
        ans = 0;

        // for(int i = 0; i < 10; ++i){
        //     printf("%d ", query(i) - query(i - 1));
        // }printf("\n");

        if(query(0) != 0){
            for(int i = MAXLOG-1; i >= 0; --i){
                int pot2 = (1 << i);
                int pos = ans + pot2;
                if(pos < MAXV){
                    int val = query(pos);
                    // cerr << val << " " << pos + 1 << endl;
                    if(val == (pos + 1)) ans += pot2;
                }
            }
            ans++;
        }

        // cerr << "::" << ans << endl;
        update(ans, 1);
    }
    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];
        bool pbn_on = (query(pos_maybe_next) - query(pos_maybe_next - 1)) == 1;
        // cerr << "::" << maybe_next << " " << pos_maybe_next << " " << pbn_on << endl;
        if(pbn_on){
            curr = maybe_next;
            // cerr << ":::" << curr << " " << i << " " << (1 << i) << endl;
        }
    }

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

    update(id_pos[curr], -1);

    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:43: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:77: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:112:12: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
     return ans;
            ^~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:157: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