oj.uz

Submission #524343

# Submission time Handle Problem Language Result Execution time Memory
524343 2022-02-09T04:51:38 Z AA_Surely Ball Machine (BOI13_ballmachine) C++17
16.1111 / 100
 263 ms 25052 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];
VI adj[MAXN], order;

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);
    }
    F0R(i, n) sort(ALL(adj[i]));
    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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4172 KB Output isn't correct
2 Incorrect 112 ms 12528 KB Output isn't correct
3 Incorrect 66 ms 12608 KB Output isn't correct
4 Incorrect 2 ms 4192 KB Output isn't correct
5 Incorrect 3 ms 4172 KB Output isn't correct
6 Incorrect 3 ms 4300 KB Output isn't correct
7 Incorrect 3 ms 4300 KB Output isn't correct
8 Incorrect 3 ms 4300 KB Output isn't correct
9 Incorrect 7 ms 4684 KB Output isn't correct
10 Incorrect 20 ms 6332 KB Output isn't correct
11 Incorrect 103 ms 12472 KB Output isn't correct
12 Incorrect 83 ms 12664 KB Output isn't correct
13 Incorrect 86 ms 12452 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 8340 KB Output is correct
2 Incorrect 233 ms 20532 KB Output isn't correct
3 Incorrect 86 ms 16940 KB Output isn't correct
4 Incorrect 98 ms 9392 KB Output isn't correct
5 Incorrect 121 ms 9220 KB Output isn't correct
6 Incorrect 114 ms 9260 KB Output isn't correct
7 Incorrect 113 ms 8468 KB Output isn't correct
8 Correct 45 ms 8344 KB Output is correct
9 Incorrect 193 ms 20792 KB Output isn't correct
10 Incorrect 226 ms 20584 KB Output isn't correct
11 Incorrect 199 ms 20484 KB Output isn't correct
12 Incorrect 215 ms 18668 KB Output isn't correct
13 Correct 101 ms 22712 KB Output is correct
14 Incorrect 78 ms 16928 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 80 ms 12700 KB Output isn't correct
2 Incorrect 257 ms 19120 KB Output isn't correct
3 Correct 151 ms 20956 KB Output is correct
4 Incorrect 132 ms 17788 KB Output isn't correct
5 Incorrect 168 ms 17448 KB Output isn't correct
6 Incorrect 164 ms 17480 KB Output isn't correct
7 Incorrect 143 ms 16188 KB Output isn't correct
8 Correct 149 ms 20992 KB Output is correct
9 Incorrect 193 ms 21012 KB Output isn't correct
10 Incorrect 259 ms 20768 KB Output isn't correct
11 Incorrect 243 ms 20528 KB Output isn't correct
12 Incorrect 237 ms 19012 KB Output isn't correct
13 Correct 240 ms 25052 KB Output is correct
14 Incorrect 108 ms 16836 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 228 ms 21032 KB Output isn't correct
2 Incorrect 263 ms 18996 KB Output isn't correct
3 Correct 119 ms 24952 KB Output is correct
4 Incorrect 214 ms 21060 KB Output isn't correct
5 Incorrect 252 ms 20544 KB Output isn't correct
6 Incorrect 207 ms 20432 KB Output isn't correct
7 Incorrect 231 ms 18944 KB Output isn't correct
8 Correct 125 ms 25020 KB Output is correct
9 Incorrect 78 ms 16832 KB Output isn't correct