Submission #667143

#	Time	Username	Problem	Language	Result	Execution time	Memory
667143		ar_paixaos19	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	455 ms	28624 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;
    }
    
    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){
    for(int k = LOGN - 1; k >= 0; k--){
        int l = tout[ up[k][v] ];
        if(!query(1, 1, n, l)){
            //printf("deu no k = %d\n", k);
            v = up[k][v];
        }
    }

    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 'int main()':
ballmachine.cpp:146:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |     int n, q; scanf("%d %d", &n, &q);
      |               ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp:150:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |         int v; scanf("%d", &v);
      |                ~~~~~^~~~~~~~~~
ballmachine.cpp:167:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  167 |         int type; scanf("%d", &type);
      |                   ~~~~~^~~~~~~~~~~~~
ballmachine.cpp:170:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |             int k; scanf("%d", &k);
      |                    ~~~~~^~~~~~~~~~
ballmachine.cpp:177:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |             int x; scanf("%d", &x);
      |                    ~~~~~^~~~~~~~~~
ballmachine.cpp:163:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  163 |     dfs(root, root, 1);
      |     ~~~^~~~~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5