제출 #1207018

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1207018		lxz20071231	Ball Machine (BOI13_ballmachine)	C++20	20.95 / 100	1097 ms	24164 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;

using ll = long long; using db = double;
template <class T> using v = vector<T>;
using pii = pair<int, int>; using vi = v<int>; using vpi = v<pii>; using vvi = v<vi>; using vvpi = v<vpi>;
using pll = pair<ll, ll>; using vll = v<ll>; using vpl = v<pll>; using vvl = v<vll>; using vvpl = v<vpl>;

#define mp make_pair
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end()

const int INF = 1e9;
const ll INFLL = 1e18;

const int N = 100001;
int par[N][18], depth[N], cf[N], min_node[N];
bool filled[N];
vi child[N];

set<pii> nxt;

void dfs(int u){
    cf[u] = child[u].size();
    min_node[u] = u;
    for (int v : child[u]){
        depth[v] = depth[u]+1;
        dfs(v);
        min_node[u] = min(min_node[u], min_node[v]);
    }
    if (!cf[u]) nxt.insert({min_node[u], u});
}

signed main () {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n, q, root; cin >> n >> q;
    for (int i=1; i<=n; i++){
        cin >> par[i][0];
        if (par[i][0] == 0) {root = i;}
        else child[par[i][0]].pb(i);
    }
    dfs(root);
    for (int i=1; i<18; i++){
        for (int j=1; j<=n; j++){
            par[j][i] = par[par[j][i-1]][i-1];
        }
    }
    while (q--){
        int type, x; cin >> type >> x;
        if (type == 1){
            while (x--){
                int u = (*nxt.begin()).s;
                nxt.erase(nxt.begin());
                filled[u] = true;
                int p = par[u][0];
                if (p > 0){
                    cf[p]--;
                    if (cf[p] == 0) nxt.insert({min_node[p], p});
                }
                if (x == 0){
                    cout << u << '\n';
                }
            }
        }
        else{
            int u = x;
            for (int i=17; i>=0; i--){
                if (filled[par[u][i]] && par[u][i] != 0){
                    u = par[u][i];
                }
            }
            filled[u] = false;
            nxt.insert({min_node[u], u});
            int p = par[u][0];
            if (p>0){
                cf[p]++;
                if (cf[p] == 1) nxt.erase({min_node[p], p});
            }
            cout << depth[x] - depth[u] << '\n';
        }
    }
    
    return 0;
}

• Subtask 1: 0 / 25
• Subtask 2: 10.7143 / 30
• Subtask 3: 8.5714 / 40
• Subtask 4: 1.6667 / 5