제출 #1239069

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239069		eirinayukari	Ball Machine (BOI13_ballmachine)	C++20	100 / 100	252 ms	28708 KiB

ballmachine

// XD XD
#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define el cout << "\n";

using namespace std;
using ll = long long;

const int MAXN = 1e5 + 7;
const int LG = 17;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const ll LLINF = 1e18 + 7;

template <typename T>
bool ckmin(T& a, T b) {
    return a > b ? a = b, true : false;
}

template <typename T>
bool ckmax(T& a, T b) {
    return a < b ? a = b, true : false;
}

int n, q;
vector<int> adj[MAXN];
int root;
int dep[MAXN], mn[MAXN];
int tim[MAXN], timer = 0;
int up[LG + 1][MAXN];
bool ball[MAXN];
priority_queue<pair<int, int>> pq;

void dfs1(int u) {
    mn[u] = u;
    for (int v : adj[u]) {
        dep[v] = dep[u] + 1;
        dfs1(v);
        ckmin(mn[u], mn[v]);
    }
} 

void dfs2(int u) {
    vector<pair<int, int>> s;
    for (int v : adj[u]) {
        s.emplace_back(mn[v], v);
    }

    sort(all(s));
    for (auto [m, v] : s) {
        dfs2(v);
    }

    tim[u] = ++timer;
}

void add(bool print) {
    auto [t, u] = pq.top();
    pq.pop();
    ball[u] = true;
    if (print) {
        cout << u << "\n";
    }
}

void rev(int u) {
    int anc = u;
    for (int i = LG; i >= 0; i--) {
        int p = up[i][anc]; 
        if (ball[p]) {
            anc = p;
        }
    }

    cout << dep[u] - dep[anc] << "\n";
    ball[anc] = false;
    pq.emplace(-tim[anc], anc);
}

void solve(int id) {
    // cout << "Case " << id << ": ";
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        int p;
        cin >> p;
        if (p) {
            adj[p].push_back(i);
            up[0][i] = p;
        } else {
            root = i;
        }
    }    

    dfs1(root);
    dfs2(root);
    
    for (int i = 1; i <= LG; i++) {
        for (int j = 1; j <= n; j++) {
            up[i][j] = up[i - 1][up[i - 1][j]];
        }
    }

    for (int i = 1; i <= n; i++) {
        pq.emplace(-tim[i], i);
    }

    // for (int i = 1; i <= n; i++) {
    //     cout << tim[i] << " ";
    // }

    while (q--) {
        int opt, x;
        cin >> opt >> x;
        if (opt == 1) {
            for (int i = 1; i <= x; i++) {
                add(i == x);
            }
        } else {
            rev(x);
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++) {
        solve(i);
    }
    return 0;
}

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