Submission #463824

#	Time	Username	Problem	Language	Result	Execution time	Memory
463824		JovanB	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	362 ms	24596 KiB

ballmachine

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

using ll = long long;
using ld = long double;

const int N = 100000;
const int LOG = 18;

int par[N+5][LOG+1];
int mnn[N+5];
vector <int> graf[N+5];

void dfs_calc(int v){
    mnn[v] = v;
    for(int j=1; j<=LOG; j++) par[v][j] = par[par[v][j-1]][j-1];
    for(auto c : graf[v]){
        dfs_calc(c);
        mnn[v] = min(mnn[v], mnn[c]);
    }
    sort(graf[v].begin(), graf[v].end(), [](int a, int b){ return mnn[a] < mnn[b]; });
}

int gde[N+5];
int niz[N+5];

int tjm;

void dfs(int v){
    for(auto c : graf[v]) dfs(c);
    ++tjm;
    niz[tjm] = v;
    gde[v] = tjm;
}

struct Segment{
    int sum;
    bool lazy;
} seg[4*N+5];

void propagate(int node, int l, int r){
    if(!seg[node].lazy) return;
    seg[node].sum = r-l+1;
    if(l == r){
        seg[node].lazy = 0;
        return;
    }
    seg[node*2].lazy |= seg[node].lazy;
    seg[node*2+1].lazy |= seg[node].lazy;
    seg[node].lazy = 0;
}

void mrg(int node, int l, int r){
    int mid = (l+r)/2;
    propagate(node*2, l, mid);
    propagate(node*2+1, mid+1, r);
    seg[node].sum = seg[node*2].sum + seg[node*2+1].sum;
}

void upd_range(int node, int l, int r, int tl, int tr){
    if(tl > r || l > tr) return;
    if(tl <= l && r <= tr){
        seg[node].lazy = 1;
        propagate(node, l, r);
        return;
    }
    int mid = (l+r)/2;
    upd_range(node*2, l, mid, tl, tr);
    upd_range(node*2+1, mid+1, r, tl, tr);
    mrg(node, l, r);
}

void upd_point(int node, int l, int r, int x){
    propagate(node, l, r);
    if(l == r){
        seg[node].sum = 0;
        return;
    }
    int mid = (l+r)/2;
    if(x <= mid) upd_point(node*2, l, mid, x);
    else upd_point(node*2+1, mid+1, r, x);
    mrg(node, l, r);
}

int find_first(int node, int l, int r, int k){
    if(l == r) return l;
    int mid = (l+r)/2;
    propagate(node*2, l, mid);
    propagate(node*2+1, mid+1, r);
    if(mid-l+1 - seg[node*2].sum >= k) return find_first(node*2, l, mid, k);
    return find_first(node*2+1, mid+1, r, k - (mid-l+1 - seg[node*2].sum));
}

int get_point(int node, int l, int r, int x){
    propagate(node, l, r);
    if(l == r) return seg[node].sum;
    int mid = (l+r)/2;
    if(x <= mid) return get_point(node*2, l, mid, x);
    return get_point(node*2+1, mid+1, r, x);
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
	cout.precision(10);
	cout << fixed;

    int n, qrs;
    cin >> n >> qrs;
    int root = 0;
    for(int i=1; i<=n; i++){
        cin >> par[i][0];
        if(par[i][0] == 0) root = i;
        else graf[par[i][0]].push_back(i);
    }
    dfs_calc(root);
    dfs(root);
    while(qrs--){
        int typ;
        cin >> typ;
        if(typ == 1){
            int cnt;
            cin >> cnt;
            int k = find_first(1, 1, n, cnt);
            upd_range(1, 1, n, 1, k);
            cout << niz[k] << "\n";
        }
        else{
            int v;
            cin >> v;
            int res = 0;
            for(int j=LOG; j>=0; j--) if(par[v][j] && get_point(1, 1, n, gde[par[v][j]])) res += (1 << j), v = par[v][j];
            cout << res << "\n";
            upd_point(1, 1, n, gde[v]);
        }
    }
    return 0;
}

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