제출 #643448

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
643448		devariaota	Ball Machine (BOI13_ballmachine)	C++17	16.11 / 100	142 ms	25056 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5;
const int LOG = 18;
vector<int>adj[N + 2];
bool mark[N + 2];
int n, q, root;
int p[N + 2], mini[N + 2], in[N + 2], depth[N + 2], t[N + 2];
int up[N + 2][LOG];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
int timer = 1;

bool byMin(int &a, int &b){
    return mini[a] < mini[b];
}

void dfs(int cur, int d){
    depth[cur] = d;
    up[cur][0] = p[cur];
    for(int i = 1; i < LOG; i++){
        up[cur][i] = up[up[cur][i - 1]][i - 1];
    }

    for(auto &nxt: adj[cur]){
        dfs(nxt, d + 1);
    }

    t[cur] = timer;
    pq.emplace(timer++, cur);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;

    for(int i = 1; i <= n; i++){
        cin >> p[i];
        if(p[i] == 0) root = i;
        adj[p[i]].push_back(i);
        in[p[i]]++;
    }

    queue<int>leaf;
    for(int i = 1; i <= n; i++){
        if(in[p[i]]) continue;
        mini[i] = i;

        leaf.push(i);
    }

    while(!leaf.empty()){
        int cur = leaf.front(); leaf.pop();
        int nxt = p[cur];
        mini[nxt] = min(cur, nxt);
        in[nxt]--;
        if(!in[nxt]) leaf.push(nxt);
    }

    for(int i = 1; i <= n; i++){
        if(!adj[i].empty()) sort(adj[i].begin(), adj[i].end(), byMin);
    }

    dfs(root, 0);

    while(q--){
        int a, x; cin >> a >> x;
        if(a == 1){
            for(int i = 0; i < x; i++){
                if(i + 1 == x) cout << pq.top().second << '\n';
                mark[pq.top().second] = true;
                pq.pop();
            }
        } else{
            int tmp = x;
            for(int i = LOG - 1; i >= 0; i--){
                if(mark[up[tmp][i]]) tmp = up[tmp][i];
            }

            mark[tmp] = false;
            pq.emplace(t[tmp], tmp);
            cout << depth[x] - depth[tmp] << '\n';
        }
    }

    return 0;
}

• Subtask 1: 0 / 25
• Subtask 2: 6.428571428571429 / 30
• Subtask 3: 8.571428571428571 / 40
• Subtask 4: 1.1111111111111112 / 5