Submission #950441

#	Time	Username	Problem	Language	Result	Execution time	Memory
950441		phoenix0423	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	764 ms	37224 KiB

ballmachine

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long 
const int maxn = 1e5 + 5;
int dep[maxn], succ[maxn][18], in[maxn], out[maxn], dfn = 0;
vector<int> adj[maxn];
int st[maxn * 4], tag[maxn * 4], id[maxn];
int mn[maxn];
int n, q;

void dfs1(int pos){
    mn[pos] = pos;
    for(auto x : adj[pos]){
        dfs1(x);
        mn[pos] = min(mn[pos], mn[x]);
    }
}
void dfs(int pos, int prev){
    sort(adj[pos].begin(), adj[pos].end(), [&](int a, int b){ return mn[a] < mn[b];});
    in[pos] = dfn;
    succ[pos][0] = prev;
    for(int i = 1; i < 18; i++) succ[pos][i] = succ[succ[pos][i - 1]][i - 1];
    for(auto x : adj[pos]){
        dep[x] = dep[pos] + 1;
        dfs(x, pos);
    }
    out[pos] = dfn++;
    id[out[pos]] = pos;
}

void push(int v, int l, int r){
    int m = (l + r) / 2;
    if(tag[v]){
        st[v * 2] = (m - l + 1), tag[v * 2] = 1;
        st[v * 2 + 1] = (r - m), tag[v * 2 + 1] = 1;
        tag[v] = 0;
    }
}

int add(int val, int v = 1, int l = 0, int r = n - 1){
    // cout<<"add : "<<val<<" "<<l<<" "<<r<<"\n";
    st[v] += val;
    if(l == r) return l;
    int m = (l + r) / 2;
    push(v, l, r);
    if(m - l + 1 - st[v * 2] >= val){
        return add(val, v * 2, l, m);
    }
    else{
        int lft = val - (m - l + 1 - st[v * 2]);
        st[v * 2] = m - l + 1, tag[v * 2] = 1;
        return add(lft, v * 2 + 1, m + 1, r);
    }
}

int qry(int pos, int v = 1, int l = 0, int r = n - 1){
    if(l == r) return st[v];
    int m = (l + r) / 2;
    push(v, l, r);
    if(pos <= m) return qry(pos, v * 2, l, m);
    else return qry(pos, v * 2 + 1, m + 1, r);
}

void upd(int pos, int val, int v = 1, int l = 0, int r = n - 1){
    if(l == r){
        // cout<<"upd : "<<pos<<" "<<val<<"\n";
        st[v] += val;
        return;
    }
    push(v, l, r);
    int m = (l + r) / 2;
    if(pos <= m) upd(pos, val, v * 2, l, m);
    else upd(pos, val, v * 2 + 1, m + 1, r);
    st[v] = st[v * 2] + st[v * 2 + 1];
}

int lift(int pos, int steps){
    for(int i = 17; i >= 0; i--){
        if(steps & (1 << i)) pos = succ[pos][i];
    }
    return pos;
}
signed main(void){
    // fastio;
    cin>>n>>q;
    int rt = 0;
    for(int i = 0; i < n; i++){
        int x;
        cin>>x;
        if(x == 0) rt = i;
        else x--, adj[x].pb(i);
    }
    dfs1(rt);
    dfs(rt, rt);
    // cout<<"out : ";
    // for(int i = 0; i < n; i++) cout<<out[i]<<" ";
    // cout<<"\n";
    int ttl = 0;
    for(int i = 0; i < q; i++){
        int op, k;
        cin>>op>>k;
        // cout<<"ttl : "<<qry(out[0])<<"\n";
        if(op == 1){
            cout<<id[add(k)] + 1<<"\n";
        }
        else{
            k--;
            int l = 0, r = dep[k] + 1;
            while(l + 1 < r){
                int m = (l + r) / 2;
                int id = lift(k, m);
                // cout<<"ck : "<<id<<" "<<qry(out[id])<<"\n";
                if(qry(out[id])) l = m;
                else r = m;
            }
            cout<<l<<"\n";
            int x = lift(k, l);
            upd(out[x], -1);
        }
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:105:9: warning: unused variable 'ttl' [-Wunused-variable]
  105 |     int ttl = 0;
      |         ^~~

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