Submission #1206970

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206970		lxz20071231	Ball Machine (BOI13_ballmachine)	C++20	20.95 / 100	1097 ms	20552 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];
bool filled[N];
vi child[N];
set<int> nxt;

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

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();
                nxt.erase(nxt.begin());
                filled[u] = true;
                int p = par[u][0];
                if (p > 0){
                    cf[p]--;
                    if (cf[p] == 0) nxt.insert(p);
                }
                if (x == 0) cout << u << '\n';
            }
        }
        else{
            int u = x;
            for (int i=17; i>=0; i--){
                if (filled[par[u][i]]) u = par[u][i];
            }
            filled[u] = false;
            nxt.insert(u);
            int p = par[u][0];
            if (p>0){
                cf[p]++;
                if (cf[p] == 1) nxt.erase(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