oj.uz

Submission #524357

# Submission time Handle Problem Language Result Execution time Memory
524357 2022-02-09T05:59:47 Z AA_Surely Ball Machine (BOI13_ballmachine) C++17
100 / 100
 392 ms 26188 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4172 KB Output is correct
2 Correct 217 ms 13532 KB Output is correct
3 Correct 176 ms 13664 KB Output is correct
4 Correct 2 ms 4172 KB Output is correct
5 Correct 2 ms 4204 KB Output is correct
6 Correct 5 ms 4556 KB Output is correct
7 Correct 4 ms 4300 KB Output is correct
8 Correct 5 ms 4344 KB Output is correct
9 Correct 17 ms 4860 KB Output is correct
10 Correct 45 ms 6616 KB Output is correct
11 Correct 231 ms 13504 KB Output is correct
12 Correct 188 ms 14012 KB Output is correct
13 Correct 206 ms 13452 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 8944 KB Output is correct
2 Correct 392 ms 21528 KB Output is correct
3 Correct 191 ms 17892 KB Output is correct
4 Correct 191 ms 10360 KB Output is correct
5 Correct 221 ms 9992 KB Output is correct
6 Correct 212 ms 10096 KB Output is correct
7 Correct 214 ms 9492 KB Output is correct
8 Correct 137 ms 8960 KB Output is correct
9 Correct 315 ms 22028 KB Output is correct
10 Correct 377 ms 21664 KB Output is correct
11 Correct 334 ms 21504 KB Output is correct
12 Correct 352 ms 19816 KB Output is correct
13 Correct 231 ms 23728 KB Output is correct
14 Correct 193 ms 17976 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 13460 KB Output is correct
2 Correct 371 ms 20408 KB Output is correct
3 Correct 232 ms 22084 KB Output is correct
4 Correct 200 ms 18896 KB Output is correct
5 Correct 240 ms 18616 KB Output is correct
6 Correct 231 ms 18592 KB Output is correct
7 Correct 232 ms 17216 KB Output is correct
8 Correct 234 ms 22080 KB Output is correct
9 Correct 309 ms 22188 KB Output is correct
10 Correct 379 ms 21664 KB Output is correct
11 Correct 378 ms 21692 KB Output is correct
12 Correct 376 ms 20392 KB Output is correct
13 Correct 375 ms 26188 KB Output is correct
14 Correct 235 ms 17968 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 22232 KB Output is correct
2 Correct 379 ms 20404 KB Output is correct
3 Correct 239 ms 26040 KB Output is correct
4 Correct 357 ms 22412 KB Output is correct
5 Correct 386 ms 21852 KB Output is correct
6 Correct 336 ms 21696 KB Output is correct
7 Correct 379 ms 20356 KB Output is correct
8 Correct 243 ms 26044 KB Output is correct
9 Correct 196 ms 18140 KB Output is correct