Submission #551811

#	Time	Username	Problem	Language	Result	Execution time	Memory
551811		Vladth11	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	230 ms	34080 KiB

ballmachine

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 100001;
const ll VMAX = 1001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 447;
const ll base = 31;
const ll nr_of_bits = 21;

class AIB{
public:
    int aib[NMAX + 1];
    void update(int x, int val){
        for(; x < NMAX; x += x&(-x))
            aib[x] += val;
    }
    int query(int x){
        int val = 0;
        for(; x > 0; x -= x&(-x))
            val += aib[x];
        return val;
    }
    int first(){
        int r = 0, pas = (1 << nr_of_bits), sum = 0;
        while(pas){
            if(r + pas < NMAX && sum + aib[r + pas] == r + pas){
                r += pas;
                sum += aib[r];
            }
            pas /= 2;
        }
        if(sum == r)
            r++;
        return r;
    }
}aib, primul;

vector <int> v[NMAX];
pii timp[NMAX];
int stamp = 0;
int dp[NMAX][nr_of_bits + 1];
int minim[NMAX];
int lvl[NMAX];

void DFS(int node, int p){
    minim[node] = node;
    lvl[node] = lvl[p] + 1;
    dp[node][0] = p;
    timp[node].first = ++stamp;
    for(auto x : v[node]){
        if(x == p)
            continue;
        DFS(x, node);
        minim[node] = min(minim[node], minim[x]);
    }
    timp[node].second = stamp;
}

int order[NMAX];
int cnt = 0;

bool cmp(int a, int b){
    return minim[a] < minim[b];
}
int f[NMAX];

void baga(int node, int p){
    vector <int> cv;
    for(auto x : v[node]){
        if(x == p) continue;
        cv.push_back(x);
    }
    sort(cv.begin(), cv.end(), cmp);
    for(auto x : cv){
        baga(x, node);
    }
    order[++cnt] = node;
    f[node] = cnt;
}

int taken[NMAX];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, q, i, root;
    cin >> n >> q;
    for(i = 1; i <= n; i++){
        int x;
        cin >> x;
        if(x == 0){
            root = i;
        }else{
            v[x].push_back(i);
            v[i].push_back(x);
        }
    }
    DFS(root, 0);
    for(int j = 1; j <= nr_of_bits; j++){
        for(i = 1; i <= n; i++){
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
        }
    }
    baga(root, 0);
    while(q--){
        int t, x;
        cin >> t >> x;
        if(t == 1){
            int ultim = 0;
            while(x--){
                int unde = primul.first();
                int cine = order[unde];
                ultim = cine;
                primul.update(unde, 1);
                taken[cine] = 1;
                aib.update(timp[cine].first, 1);
                aib.update(timp[cine].second + 1, -1);
            }
            cout << ultim << "\n";
        }else{
            int r = x, pas = nr_of_bits, cate = aib.query(timp[x].first);
            while(pas >= 0){
                int nxt = dp[r][pas];
                int diferenta = lvl[x] - lvl[nxt];
                if(nxt != 0 && aib.query(timp[nxt].first) + diferenta == cate && taken[nxt])
                    r = nxt;
                pas--;
            }
            primul.update(f[r], -1);
            taken[r] = 0;
            aib.update(timp[r].first, -1);
            aib.update(timp[r].second + 1, 1);
            cout << lvl[x] - lvl[r] << "\n";
        }
    }
    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:113:9: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  113 |     baga(root, 0);
      |     ~~~~^~~~~~~~~

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