Submission #667224

#	Time	Username	Problem	Language	Result	Execution time	Memory
667224		joaof	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	235 ms	41720 KiB

ballmachine

#include <bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define bug(x) cerr << #x << ": " << x << endl
#define pb push_back
using namespace std;
using ll = long long;

const int MAX = 1e5 + 10;

int prof[MAX], bl[MAX][50], sub[MAX], minSub[MAX], pai[MAX], mark[MAX], pot[50], id[MAX];

vector<int> g[MAX], ord;

set<pair<int, int>> s;

int inserir(int x){
    //bug(x);
    while(x--){
        if(x == 0){
            mark[(*s.begin()).ss] = 1;

            int ans = (*s.begin()).ss;
            s.erase((*s.begin()));
            return ans;
        }

        mark[(*s.begin()).ss] = 1;
        s.erase((*s.begin()));
    }

    return 4;
}

int remover(int x){
    int ans = 0;

    for(int i = 20; i >= 0; i--){
        if(bl[x][i] == 0 || mark[bl[x][i]] == 0) continue;
        ans += pot[i];

        // bug(pot[i]);
        x = bl[x][i];
        // bug(x);
    }

    mark[x] = 0;

    s.insert({id[x], x});

    return ans;
}

bool cmp(int a, int b){
    return minSub[a] < minSub[b];
}

void calcLift(int x){
    bl[x][0] = pai[x];
    int t = 0;
    while(bl[x][t] != 0){
        t++;
        bl[x][t] = bl[bl[x][t - 1]][t - 1];
    }
}

void dfs(int x, int type){
    if(type == 1){
        sub[x] = 1;
        minSub[x] = x;
        for(auto v : g[x]){
            prof[v] = prof[x] + 1;
            calcLift(v);
            dfs(v, 1);

            minSub[x] = min(minSub[x], minSub[v]);

            sub[x] += sub[v];
        }

        sort(all(g[x]), cmp);
    }

    if(type == 2){
        for(auto v : g[x]){
            dfs(v, 2);
        }
        ord.pb(x);
        id[x] = ord.size() - 1;
    }
}

int main(){
    pot[0] = 1;
    for(int i = 1; i <= 25; i++){
        pot[i] = 2 * pot[i - 1];
    }

    int n, q, root;

    scanf("%d %d", &n, &q);

    for(int i = 1; i <= n; i++){
        int a;
        scanf("%d", &a);

        if(a == 0){
            root = i;

            continue;
        }

        pai[i] = a;

        g[a].pb(i);
    }

    dfs(root, 1);

    dfs(root, 2);

    for(int i = 0; i < ord.size(); i++){
        s.insert({i, ord[i]});

        // bug(ord[i]);
    }

    for(int i = 1; i <= q; i++){
        int op, a;
        scanf("%d %d", &op, &a);

        if(op == 1){
            printf("%d\n", inserir(a));
        }
        if(op == 2){
            printf("%d\n", remover(a));
        }
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:123:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for(int i = 0; i < ord.size(); i++){
      |                    ~~^~~~~~~~~~~~
ballmachine.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         scanf("%d", &a);
      |         ~~~~~^~~~~~~~~~
ballmachine.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |         scanf("%d %d", &op, &a);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
ballmachine.cpp:121:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  121 |     dfs(root, 2);
      |     ~~~^~~~~~~~~

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