제출 #1291369

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291369		qrn	Ball Machine (BOI13_ballmachine)	C++20	100 / 100	351 ms	46264 KiB

ballmachine

// one expects wise words here, but what can one do when they cannot find words to express their thoughts?
// just staring at the messy code below, arent you? well, im supposed to improve, not jibber jabber here.
// perhaps one does not have a choice when he does not enjoy anything, so he just yaps to himself in vsc like a loser.
// ome47

#include "bits/stdc++.h"
using namespace std;
#define intt long long

const intt mxN = 2e5 + 5;
const intt LG = 20;
const intt inf = 1e18;

vector<vector<intt>> graph, up;
vector<intt> par(mxN), isfull(mxN), depth(mxN), wave(mxN), cnt(mxN), val(mxN);
set<pair<intt,intt>> avil;
intt n, q, timer, root;

void dfs(intt node, intt parent) {
    val[node] = node;
    up[0][node] = parent;
    for(intt i = 1; i <= LG; i++) {
        up[i][node] = up[i-1][up[i-1][node]];
    }

    for(auto u : graph[node]) {
        if(u != parent) {
            depth[u] = depth[node] + 1;
            dfs(u, node);
            val[node] = min(val[node], val[u]);
        }
    }
}

void dfs2(intt node, intt parent) {
    for(auto u : graph[node]) {
        if(u != parent) {
            dfs2(u, node);
        }
    }
    wave[node] = timer++;
}

bool cmp(intt &a, intt &b) {
    if(val[a] == val[b]) {
        return a < b;
    }
    return val[a] < val[b];
}

intt bl(intt node, intt k) {
    for(intt i = LG - 1; i >= 0; i--) {
        if((1 << i) & k) {
            node = up[i][node];
        }
    }
    return node;
}

void _() {
    cin >> n >> q;
    graph.assign(n + 1, vector<intt> {});
    up.assign(LG + 1, vector<intt>(n + 1, 0ll));

    for(intt i = 1; i <= n; i++) {
        intt node; cin >> node;
        if(node == 0) {
            root = i;
            par[root] = 0;
        } else {
            graph[node].push_back(i);
            graph[i].push_back(node);
            par[i] = node;
        }
    }

    dfs(root, par[root]);
    for(intt i = 1; i <= n; i++) {
        sort(graph[i].begin(), graph[i].end(), cmp);
    }
    dfs2(root, par[root]);
    for(intt i = 1; i <= n; i++) {
        cnt[i] = graph[i].size();
        if(i != root) --cnt[i];
        if(cnt[i] == 0) {
            avil.insert({wave[i], i});
        }
    }   

    while(q--) {
        intt type, x, ans = 0;
        cin >> type >> x;
        if(type == 1) {
            // cout << "INITALLY: " << endl;
            // for(auto h : avil) {
            //     cout << h.first << " " << h.second << endl;
            // }
            for(intt i = 0; i < x; i++) {
                if(avil.empty()) break;
                pair<intt,intt> p = *avil.begin();
                intt leaf = p.second;
                isfull[leaf] = 1;
                cnt[par[leaf]]--;
                avil.erase(avil.begin());
                ans = leaf;
                if(leaf != root && !cnt[par[leaf]]) {
                    avil.insert({wave[par[leaf]], par[leaf]});
                }
                // cout << "AFTER " << i << ": " << endl;
                // for(auto h : avil) {
                //     cout << h.first << " " << h.second << endl;
                // }
            }
        } else {
            intt l = 1, r = depth[x], anc = x;
            while(l <= r) {
                intt mid = (l + r) / 2;
                intt cand = bl(x, mid);
                // cout << "BS: " << mid << " " << cand << endl;
                if(isfull[cand]) {
                    anc = cand;
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            // cout << x << " " << anc << endl;
            if(anc != root) {
               cnt[par[anc]]++;
            }
            avil.insert({wave[anc], anc});
            isfull[anc] = 0;
            ans = depth[x] - depth[anc];
        }
        cout << ans << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    intt t = 1;
    // cin >> t;
    while(t--){
        cout << endl;
        _();
    }
}
// ⠀⠀⠀⠀⠀⠀⠀⢀⣤⣦⣶⣤⠀⠀⠀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⣤⢀⣀⡀⣠⣄⣠⣶⣿⣿⣿⣿⣿⣿⣿⣷⣾⡦⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⠻⡳⢛⠛⠒⠚⢛⣿⣿⠟⠋⠉⠛⠛⢿⣿⣿⣿⠇⠀⠀⠀⠀⠀⠀⠀⠀
// ⢛⡛⢿⣿⠟⠻⠛⣿⣇⣶⣖⣤⣀⣄⡰⣹⣿⡟⠁⠀⠀⠀⠀⠀⠀⠀⠀
// ⢿⠿⠿⠿⠿⠿⠿⢭⣐⠠⢼⣬⠽⢈⢁⡿⠛⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀
// ⣛⣱⣤⣤⣤⣀⣄⣄⣗⢌⠋⠉⢙⣴⣧⢤⣤⣤⣤⣦⡀⠀⠀⠀⠀⢺⡿
// ⣿⣿⣿⠟⠛⠋⠀⡬⠼⢠⠍⠂⠀⠨⡇⠀⡏⠉⠛⢿⣧⠀⠀⠀⠀⢸⣀
// ⣟⠄⠀⠀⠀⠀⠀⢡⠀⠀⠀⠀⠀⡠⠁⢀⠁⠀⠀⠀⠘⣗⢀⠄⢶⣼⣾
// ⠀⠀⠀⢠⣦⠇⠀⠀⠁⠒⠒⠒⠈⠀⠀⠀⣞⢶⡀⠀⠀⠹⣧⣠⡞⣸⣏
// ⠀⠀⢀⡞⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⣿⣿⣦⡀⠀⠈⠫⣕⣻⡇
// ⠀⠀⣾⣧⠈⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⣿⣿⣿⣷⣦⡠⡤⠀⣿⡇
// ⠠⢿⣿⣿⠂⠀⠀⠀⠀⠀⠀⠀⠀⣀⣀⠀⠴⣿⣿⣿⣿⠟⠋⢀⣤⣿⣷
// ⣀⣀⣀⣙⣃⣠⣤⣔⣤⣢⣵⣒⣒⣢⣄⣤⣄⣛⣋⣉⣀⣀⣤⣿⣿⣿⣿

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