# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
242123 | 2020-06-26T22:19:51 Z | pauloamed | Ball Machine (BOI13_ballmachine) | C++14 | 211 ms | 20728 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; scanf("%d %d", &n, &q); int root; for(int i = 0; i < n; ++i){ int x; scanf("%d", &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; scanf("%d", &x); if(x == 1){ int k; scanf("%d", &k); printf("%d\n", pos_id[add(k)] + 1); }else{ int y; scanf("%d", &y); printf("%d\n", remove(y - 1)); } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 10240 KB | Output is correct |
2 | Correct | 118 ms | 12792 KB | Output is correct |
3 | Correct | 87 ms | 12792 KB | Output is correct |
4 | Correct | 17 ms | 10240 KB | Output is correct |
5 | Correct | 16 ms | 10368 KB | Output is correct |
6 | Correct | 17 ms | 10240 KB | Output is correct |
7 | Correct | 19 ms | 10368 KB | Output is correct |
8 | Correct | 18 ms | 10240 KB | Output is correct |
9 | Correct | 23 ms | 10496 KB | Output is correct |
10 | Correct | 35 ms | 10880 KB | Output is correct |
11 | Correct | 129 ms | 12792 KB | Output is correct |
12 | Correct | 87 ms | 12792 KB | Output is correct |
13 | Correct | 114 ms | 12536 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 62 ms | 12280 KB | Output is correct |
2 | Correct | 198 ms | 16760 KB | Output is correct |
3 | Correct | 102 ms | 13556 KB | Output is correct |
4 | Correct | 92 ms | 12408 KB | Output is correct |
5 | Correct | 95 ms | 12280 KB | Output is correct |
6 | Correct | 90 ms | 12280 KB | Output is correct |
7 | Correct | 85 ms | 11768 KB | Output is correct |
8 | Correct | 64 ms | 12280 KB | Output is correct |
9 | Correct | 188 ms | 17144 KB | Output is correct |
10 | Correct | 192 ms | 16760 KB | Output is correct |
11 | Correct | 173 ms | 16504 KB | Output is correct |
12 | Correct | 154 ms | 15352 KB | Output is correct |
13 | Correct | 118 ms | 18984 KB | Output is correct |
14 | Correct | 96 ms | 13424 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 91 ms | 13944 KB | Output is correct |
2 | Correct | 184 ms | 15864 KB | Output is correct |
3 | Correct | 125 ms | 18424 KB | Output is correct |
4 | Correct | 120 ms | 15864 KB | Output is correct |
5 | Correct | 128 ms | 15480 KB | Output is correct |
6 | Correct | 126 ms | 15480 KB | Output is correct |
7 | Correct | 139 ms | 14584 KB | Output is correct |
8 | Correct | 152 ms | 18552 KB | Output is correct |
9 | Correct | 183 ms | 17504 KB | Output is correct |
10 | Correct | 180 ms | 17144 KB | Output is correct |
11 | Correct | 189 ms | 17144 KB | Output is correct |
12 | Correct | 174 ms | 15864 KB | Output is correct |
13 | Correct | 199 ms | 20728 KB | Output is correct |
14 | Correct | 138 ms | 13940 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 190 ms | 17400 KB | Output is correct |
2 | Correct | 211 ms | 15736 KB | Output is correct |
3 | Correct | 128 ms | 20216 KB | Output is correct |
4 | Correct | 200 ms | 17400 KB | Output is correct |
5 | Correct | 205 ms | 16892 KB | Output is correct |
6 | Correct | 149 ms | 16632 KB | Output is correct |
7 | Correct | 184 ms | 15736 KB | Output is correct |
8 | Correct | 124 ms | 20216 KB | Output is correct |
9 | Correct | 107 ms | 13684 KB | Output is correct |