Submission #524357

#	Time	Username	Problem	Language	Result	Execution time	Memory
524357		AA_Surely	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	392 ms	26188 KiB

ballmachine

#include <bits/stdc++.h>

#define FOR(i,x,n) 	for(int i=x; i<n; i++)
#define F0R(i,n) 	FOR(i,0,n)
#define ROF(i,x,n) 	for(int i=n-1; i>=x; i--)
#define R0F(i,n) 	ROF(i,0,n)

#define WTF 		cout << "WTF" << endl

#define IOS 		ios::sync_with_stdio(false); cin.tie(0)
#define F 			first
#define S	 		second
#define pb 			push_back

#define ALL(x) 		x.begin(), x.end()
#define RALL(x) 	x.rbegin(), x.rend()

using namespace std;
typedef long long 		LL;

typedef pair<int, int> 	PII;
typedef pair<LL, LL> 	PLL;

typedef vector<int> 	VI;
typedef vector<LL> 		VLL;
typedef vector<PII> 	VPII;
typedef vector<PLL> 	VPLL;

const int MAXN = 1e5 + 7;
const int ALPHA = 27;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int LOG = 22;

int n, q, rt;
int up[MAXN][LOG], tree[MAXN << 2], lazy[MAXN << 2];
int place[MAXN], height[MAXN], mn[MAXN];
VI adj[MAXN], order;

int mdf(int now_on) {
    mn[now_on] = now_on;
    for(int on : adj[now_on])
        mn[now_on] = min(mn[now_on], mdf(on));
    return mn[now_on];
}

void dfs(int now_on, int h = 0) {
    height[now_on] = h;
    for(int on : adj[now_on]) {
        up[on][0] = now_on;
        dfs(on, h + 1);
    }
    order.pb(now_on);
    place[now_on] = order.size() - 1;
    return;
}

void precalc() {
    up[rt][0] = up[n][0] = n;
    FOR(k, 1, LOG) F0R(i, n + 1) 
        up[i][k] = up[ up[i][k - 1] ][k - 1];
    return;
}

void init() {
    cin >> n >> q;
    fill(lazy, lazy + (MAXN << 2), -1);

    F0R(i, n) {
        int p; cin >> p;
        if (!p) {
            rt = i;
            continue;
        }

        p--; adj[p].pb(i);
    }

    mdf(rt);
    F0R(i, n) sort(ALL(adj[i]), [](int a, int b) {return mn[a] < mn[b];});
    return;
}

void build(int now_on = 1, int ls = 0, int rs = n - 1) {
    tree[now_on] = (rs - ls + 1);
    if (ls == rs) return;
    int mid = (ls + rs) >> 1;
    build(now_on << 1, ls, mid); build(now_on << 1 | 1, mid + 1, rs);
    return;
}

void shift(int now_on, int l, int r) {
    if (lazy[now_on] == -1) return;
    
    int mid = (l + r) >> 1;
    tree[now_on << 1] = (mid - l + 1) * (1 - lazy[now_on]);
    lazy[now_on << 1] = lazy[now_on];

    tree[now_on << 1 | 1] = (r - mid) * (1 - lazy[now_on]);
    lazy[now_on << 1 | 1] = lazy[now_on];

    lazy[now_on] = -1;
    return;
}

void change(int lq, int rq, int val, int now_on = 1, int ls = 0, int rs = n - 1) {
    if (rq < lq || rq < ls || rs < lq) 
        return;

    if (lq <= ls && rs <= rq) {
        tree[now_on] = (rs - ls + 1) * (1 - val);
        lazy[now_on] = val;
        return;
    }

    int mid = (ls + rs) >> 1;
    shift(now_on, ls, rs);

    change(lq, rq, val, now_on << 1, ls, mid);
    change(lq, rq, val, now_on << 1 | 1, mid + 1, rs);

    tree[now_on] = tree[now_on << 1] + tree[now_on << 1 | 1];
    return;
}

int get(int id, int now_on = 1, int ls = 0, int rs = n - 1) {
    if (ls == rs) return tree[now_on];
    int mid = (ls + rs) >> 1;
    shift(now_on, ls, rs);
    if (id <= mid) return get(id, now_on << 1, ls, mid);
    return get(id, now_on << 1 | 1, mid + 1, rs);
}

int kzer(int num, int now_on = 1, int ls = 0, int rs = n - 1) {
    if (ls == rs) return ls;
    int mid = (ls + rs) >> 1;
    shift(now_on, ls, rs);
    if (num <= tree[now_on << 1]) return kzer(num, now_on << 1, ls, mid);
    return kzer(num - tree[now_on << 1], now_on << 1 | 1, mid + 1, rs);
}

int fdLstFull(int x) {
    int on = x;
    R0F(i, LOG) if (up[on][i] != n && !get(place[ up[on][i] ]))
        on = up[on][i];
    return on;
}

//#define endl '\n'

void handleQuery() {
    int tp; cin >> tp;
    if (tp == 1) {
        int k; cin >> k;
        int lst = kzer(k);
        //cout << "lst: " << lst << endl;
        change(0, lst, 1);
        cout << order[lst] + 1 << endl;
        /*
        F0R(i, n) cout << get(i) << ' ';
        cout << endl;
        */
        return;
    }

    int x; cin >> x; x--;
    int nd = fdLstFull(x);
    cout << height[x] - height[nd] << endl;
    change(place[nd], place[nd], 0);
    /*
    F0R(i, n) cout << get(i) << ' ';
    cout << endl;
    */
    return;
}

int main() {
    IOS;
    
    init();
    /*
    F0R(i, n) {
        cout << i + 1 << " : ";
        for(int on : adj[i]) cout << on + 1 << ' ';
        cout << endl;
    }
    */
    dfs(rt);
    /*
    for(int on : order) cout << on + 1 << ' ';
    cout << endl;
    */
    precalc();
    build();
    /*
    F0R(i, n) cout << get(i) << ' ';
    cout << endl;
    */
    while(q--) handleQuery();
}

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