제출 #617957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
617957		qualdum	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	444 ms	42324 KiB

ballmachine

#include "bits/stdc++.h"

using namespace std;

#define int long long
#define sz(v) ((int)(v).size())
#define all(a) (a).begin(),  (a).end()
#define rall(a) a.rbegin(), a.rend()
#define F first
#define S second
#define time (double)clock() / (double)CLOCKS_PER_SEC

using pii = pair<int, int>;
using ll = long long;
using ld = long double;

const ll infll = (ll)4e18 + 27;
const ll inf = (ll)1e9 + 27;
const ll mod = (ll)1e9 + 7;

#ifdef home
#define dbg(x) cout << #x << " = " << (x) << endl
#else
#define dbg(x) 228
#endif

template <class T>
using pq = priority_queue <T, vector <T>, less <T>>;
template <class T>
using pqr = priority_queue <T, vector <T>, greater <T>>;

template <typename T, typename T2>
istream& operator>> (istream& in, pair<T, T2>& b) {
    in >> b.first >> b.second;
    return in;
}

template <typename T, typename T2>
ostream& operator<< (ostream& out, const pair<T, T2>& b) {
    out << "{" << b.first << ", " << b.second << "}";
    return out;
}

template <typename T>
istream& operator>> (istream& in, vector<T>& b) {
    for(auto &v: b) {
        in >> v;
    }
    return in;
}

template <typename T>
ostream& operator<< (ostream& out, vector<T>& b) {
    for(auto &v: b) {
        out << v << ' ';
    }
    return out;
}

template <typename T>
ostream& operator<< (ostream& out, deque<T>& b) {
    for(auto &v: b) {
        out << v << ' ';
    }
    return out;
}

template <typename T>
void print(T x, string end = "\n") {
    cout << x << end;
}

template <typename T1, typename T2> bool chkmin(T1 &x, const T2 &y) { return x > y && (x = y, true); }
template <typename T1, typename T2> bool chkmax(T1 &x, const T2 &y) { return x < y && (x = y, true); }

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N = 1e5 + 10, LOG = 20;
int up[N][LOG];
vector<int> g[N];
set<pii> st;
int timer[N], cur = 1;
bool ok[N];
int h[N];

int calc(int u){
    int mn = inf;
    vector<pii> nw;
    for(int i = 0;i < sz(g[u]);i++){
        int x = calc(g[u][i]);
        nw.push_back({x, g[u][i]});
        mn = min(mn, x);
    }
    sort(all(nw));
    g[u].clear();
    for(auto [x, y]: nw){
        g[u].push_back(y);
    }
    mn = min(mn, u);
    return mn;
}

void dfs(int u, int p = -1){
    h[u] = (p == -1 ? 0 : h[p] + 1);
    for(int i = 0;i < LOG - 1;i++){
        up[u][i + 1] = up[up[u][i]][i];
    }
    for(auto v: g[u]){
        up[v][0] = u;
        dfs(v, u);
    }
    timer[u] = cur++;
    st.insert({timer[u], u});
}

int add(int k){
    int last = -1;
    for(int i = 0;i < k;i++){
        auto [x, y] = *st.begin();
        st.erase(st.begin());
        last = y;
        ok[y] = true;
    }
    return last;
}

int remove(int k){
    int doll = 0;
    int u = k;
    int t = up[u][LOG - 1];
    if(ok[t]){
        ok[t] = false;
        st.insert({timer[t], t});
        return h[k];
    }
    for(int i = LOG - 1;i >= 0;i--){
        if(ok[up[u][i]]){
            u = up[u][i];
            doll += (1ll << i);
        }
    }
    if(u == k){
        ok[u] = false;
        st.insert({timer[u], u});
        return 0;
    }
    ok[u] = false;
    st.insert({timer[u], u});
    return doll;
}

void solve() {
    int n, q;
    cin >> n >> q;
    int root = 0;
    for(int i = 1;i <= n;i++){
        int x;
        cin >> x;
        if(x == 0){
            root = i;
        } else {
            g[x].push_back(i);
        }
    }
    calc(root);
    up[root][0] = root;
    dfs(root);
    while (q--){
        int t, k;
        cin >> t >> k;
        if(t == 1){
            cout << add(k) << endl;
        } else {
            cout << remove(k) << endl;
        }
    }
}

int32_t main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cout << fixed << setprecision(15);
    int32_t t = 1;
    //cin >> t;
#ifndef home
    //freopen("fcount.in", "r", stdin);
    //freopen("fcount.out", "w", stdout);
#endif
    while(t--)
        solve();
#ifdef home
    cout << "_________________________________" << endl;
    cout << "finished in " << time << " s";
#endif
    return 0;
}

/*
8 18
2
0
1
1
3
3
4
6
1 8
2 8
2 8
2 8
2 8
2 8
2 7
2 7
2 5
1 8
2 8
2 8
2 8
2 8
2 8
2 7
2 7
2 5
 */

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