Submission #667106

#	Time	Username	Problem	Language	Result	Execution time	Memory
667106		ar_paixaos19	Ball Machine (BOI13_ballmachine)	C++17	30.67 / 100	1088 ms	28444 KiB

ballmachine

    #include <bits/stdc++.h>
    using namespace std;
     
    const int MAXN = 100010;
    const int LOGN = 20;
     
    struct node{
        int sum, lz;
     
        node(){
            sum = 0;
            lz = -1;
        }
    };
     
    int t = 0;
    int tin[MAXN], tout[MAXN], submin[MAXN], posicao[MAXN], pai[MAXN], dist[MAXN];
    node seg[4 * MAXN];
    int up[LOGN+10][MAXN];
    vector<int> grafo[MAXN];
     
    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 refresh(int pos, int ini, int fim){
        if(seg[pos].lz == -1){
            //printf("deu em %d\n", pos);
            return;
        }
        if(ini == fim){
            seg[pos].sum = seg[pos].lz;
            seg[pos].lz = -1;
            return;
        }
        int e = 2 * pos, d = 2 * pos + 1;
     
        seg[e].lz = seg[pos].lz;
        seg[d].lz = seg[pos].lz;
     
        seg[pos].sum = (fim - ini + 1) * seg[pos].lz;
        seg[pos].lz = -1;
        return;
    }
     
    void update(int pos, int ini, int fim, int l, int r, int val){
        refresh(pos, ini, fim);
        if(ini > r || fim < l) return;
        if(l <= ini && fim <= r){
            seg[pos].lz = val;
            refresh(pos, ini, fim);
            return;
        }
     
        int m = (ini + fim) / 2;
        int e = 2 * pos, d = 2 * pos + 1;
     
        update(e, ini, m, l, r, val);
        update(d, m + 1, fim, l, r, val);
     
        seg[pos].sum = seg[e].sum + seg[d].sum;
        return;
    }
     
    int bsseg(int pos, int ini, int fim, int s){
        if(ini == fim){
            return ini;
        }
        refresh(pos, ini, fim);
     
        int m = (ini + fim) / 2;
        int e = 2 * pos, d = 2 * pos + 1;
     
        refresh(e, ini, m), refresh(d, m + 1, fim);
     
        if(seg[e].sum >= s) return bsseg(e, ini, m, s);
        return bsseg(d, m + 1, fim, s - seg[e].sum);
    }
     
    int query(int pos, int ini, int fim, int id){
        if(id < ini || id > fim) return 0;
        if(seg[pos].lz != -1){
            int resp = seg[pos].lz;
            refresh(pos, ini, fim);
            return resp;
        }
        refresh(pos, ini, fim);
        if(ini == fim) return seg[pos].sum;
     
        int m = (ini + fim) / 2;
        int e = 2 * pos, d = 2 * pos + 1;
        if(id <= m) return query(e, ini, m, id);
        return query(d, m + 1, fim, id);
    }
     
    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){

     
        return v;
    }
     
    int main(){
        int n, q; scanf("%d %d", &n, &q);
        int root;
        update(1, 1, n, 1, n, 1);
        for(int i = 1; i <= n; i++){
            int v; scanf("%d", &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 <= q; i++){
            int type; scanf("%d", &type);
     
            if(type == 1){
                int k; scanf("%d", &k);
     
                int t = bsseg(1, 1, n, k);
                printf("%d\n", posicao[t]);
                update(1, 1, n, 1, t, 0);
            }
            if(type == 2){
                int x; scanf("%d", &x);
     
                int r = bsbl(x, n);
                printf("%d\n", dist[x] - dist[r]);
                update(1, 1, n, tout[r], tout[r], 1);
            }
        }
     
        /*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;
    }

Compilation message (stderr)

ballmachine.cpp: In function 'void dfs(int, int, int)':
ballmachine.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int i = 0; i < grafo[v].size(); i++){
      |                        ~~^~~~~~~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:140:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |         int n, q; scanf("%d %d", &n, &q);
      |                   ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp:144:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |             int v; scanf("%d", &v);
      |                    ~~~~~^~~~~~~~~~
ballmachine.cpp:161:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |             int type; scanf("%d", &type);
      |                       ~~~~~^~~~~~~~~~~~~
ballmachine.cpp:164:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |                 int k; scanf("%d", &k);
      |                        ~~~~~^~~~~~~~~~
ballmachine.cpp:171:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |                 int x; scanf("%d", &x);
      |                        ~~~~~^~~~~~~~~~
ballmachine.cpp:157:12: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  157 |         dfs(root, root, 1);
      |         ~~~^~~~~~~~~~~~~~~

• Subtask 1: 3.8461538461538463 / 25
• Subtask 2: 25.714285714285715 / 30
• Subtask 3: 0 / 40
• Subtask 4: 1.1111111111111112 / 5