제출 #1159277

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1159277		dosts	Ball Machine (BOI13_ballmachine)	C++20	93.89 / 100	262 ms	137060 KiB

ballmachine

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 2e16,N = 1e6+1,MOD =  998244353;

vi edges[N],d(N),tin(N),order(N),mn(N),anti(N),col(N);
int up[N][20];
int ctr = 0;
int timer = 1;

void dfs(int node,int p) {
    if (node == p) d[node] = 0;
    else d[node] = d[p]+1;
    tin[node] = timer++;
    up[node][0] = p;
    mn[node] = node;
    for (int i=1;i<20;i++) up[node][i] = up[up[node][i-1]][i-1];
    for (auto it : edges[node]) {
        dfs(it,node);
        mn[node] = min(mn[node],mn[it]);
    }
}

void dfs2(int node,int p) {
    vi ch;
    for (auto it : edges[node]) {
        ch.push_back(it);
    }
    sort(all(ch),[&](int x,int y){
        return mn[x] < mn[y];
    });
    for (auto it : ch) dfs2(it,node);
    order[node] = ++ctr;
    anti[order[node]] = node;
}


struct ST {
    vi t;
    ST(int nn) {
        t.assign(4*nn+1,0);
    }

    void update(int node,int l,int r,int p,int v) {
        if (l == r) {
            t[node] = v;
            return;
        }
        int m = (l+r) >> 1;
        if (p<=m) update(2*node,l,m,p,v);
        else update(2*node+1,m+1,r,p,v);
        t[node] = t[2*node]+t[2*node+1];
    }

    int walk(int node,int l,int r) {
        if (t[node] == r-l+1) return 0;
        if (l == r) return l;
        int m = (l+r) >> 1;
        int wl = walk(2*node,l,m);
        if (!wl) return walk(2*node+1,m+1,r);
        return wl;
    }
} st(N);

int n,q;
int addball() {
    int wlk = st.walk(1,1,n);
    return anti[wlk];
};

int remball(int nd) {
    assert(col[nd]);
    for (int j = 19;j>=0;j--) {
        if (col[up[nd][j]]) nd = up[nd][j];
    }
    return nd;
}

void solve() {
    cin >> n >> q;
    int root;
    for (int i=1;i<=n;i++) {
        int p;
        cin >> p;
        if (!p) {
            root = i;
        }
        else edges[p].push_back(i);
    }
    dfs(root,root);
    dfs2(root,root);
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int k;
            cin >> k;
            int lstball = 0;
            while (k--) {
                int ball = addball();
                lstball = ball;
                st.update(1,1,n,order[ball],1);
                col[ball] = 1;
            }
            cout << lstball << endl;
        }
        else {
            int nd;
            cin >> nd;
            int rm = remball(nd);
            st.update(1,1,n,order[rm],0);
            col[rm] = 0;
            cout << d[nd]-d[rm] << endl;
        }
    }
}



int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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