oj.uz

Submission #547256

# Submission time Handle Problem Language Result Execution time Memory
547256 2022-04-10T06:13:32 Z Jomnoi Ball Machine (BOI13_ballmachine) C++17
100 / 100
 176 ms 23912 KB 
#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

const int MAX_N = 1e5 + 10;

int timer;
vector <int> graph[MAX_N];
int depth[MAX_N], parent[MAX_N][20];
int minimum[MAX_N];
int st[MAX_N], pos[MAX_N];
bool state[MAX_N];
bool tree[4 * MAX_N];

int get_min(const int &u) {
    minimum[u] = u;
    for(auto v : graph[u]) {
        depth[v] = depth[u] + 1;
        minimum[u] = min(minimum[u], get_min(v));
    }
    return minimum[u];
}

void postorder(const int &u) {
    for(auto v : graph[u]) {
        postorder(v);
    }
    timer++;
    st[u] = timer;
    pos[timer] = u;
}

void update(const int &idx, const int &l, const int &r, const int &q, const bool &v) {
    if(l == r) {
        tree[idx] = v;
        return;
    }

    int mid = (l + r) / 2;
    if(q <= mid) {
        update(idx * 2, l, mid, q, v);
    }
    else {
        update(idx * 2 + 1, mid + 1, r, q, v);
    }
    tree[idx] = (tree[idx * 2] & tree[idx * 2 + 1]);
}

int query(const int &idx, const int &l, const int &r) {
    if(l == r) {
        return l;
    }

    int mid = (l + r) / 2;
    if(tree[idx * 2] == false) {
        return query(idx * 2, l, mid);
    }
    return query(idx * 2 + 1, mid + 1, r);
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int N, Q;
    cin >> N >> Q;

    int root = 1;
    for(int i = 1; i <= N; i++) {
        cin >> parent[i][0];
        if(parent[i][0] == 0) {
            root = i;
        }
        else {
            graph[parent[i][0]].push_back(i);
        }
    }

    get_min(root);
    for(int i = 1; i <= N; i++) {
        sort(graph[i].begin(), graph[i].end(), [&](const int &a, const int &b) {
            return minimum[a] < minimum[b];
        });
    }

    postorder(root);
    depth[0] = -1;
    for(int j = 1; j < 20; j++) {
        for(int i = 1; i <= N; i++) {
            parent[i][j] = parent[parent[i][j - 1]][j - 1];
        }
    }

    while(Q--) {
        int t, idx;
        cin >> t;
        if(t == 1) {
            int k;
            cin >> k;
            while(k > 0) {
                idx = query(1, 1, N);

                while(k > 0 and state[pos[idx]] == false) {
                    state[pos[idx]] = true;
                    update(1, 1, N, idx, true);
                    k--;
                    idx++;
                }
            }
            cout << pos[idx - 1] << '\n';
        }
        else {
            int x;
            cin >> x;
            int u = x;
            for(int i = 19; i >= 0; i--) {
                if(state[parent[u][i]] == true) {
                    u = parent[u][i];
                }
            }
            state[u] = false;
            update(1, 1, N, st[u], false);

            cout << depth[x] - depth[u] << '\n';   
        }
    }
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 124 ms 10136 KB Output is correct
3 Correct 59 ms 10184 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 8 ms 3156 KB Output is correct
10 Correct 22 ms 4544 KB Output is correct
11 Correct 105 ms 10236 KB Output is correct
12 Correct 59 ms 10188 KB Output is correct
13 Correct 111 ms 10560 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 6640 KB Output is correct
2 Correct 149 ms 18360 KB Output is correct
3 Correct 75 ms 13576 KB Output is correct
4 Correct 66 ms 7608 KB Output is correct
5 Correct 70 ms 7408 KB Output is correct
6 Correct 81 ms 7884 KB Output is correct
7 Correct 75 ms 6576 KB Output is correct
8 Correct 39 ms 6612 KB Output is correct
9 Correct 125 ms 18764 KB Output is correct
10 Correct 151 ms 18336 KB Output is correct
11 Correct 167 ms 18836 KB Output is correct
12 Correct 126 ms 16088 KB Output is correct
13 Correct 93 ms 20976 KB Output is correct
14 Correct 81 ms 13512 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 10760 KB Output is correct
2 Correct 159 ms 16648 KB Output is correct
3 Correct 119 ms 19460 KB Output is correct
4 Correct 90 ms 15720 KB Output is correct
5 Correct 93 ms 15276 KB Output is correct
6 Correct 96 ms 15348 KB Output is correct
7 Correct 107 ms 13744 KB Output is correct
8 Correct 108 ms 19532 KB Output is correct
9 Correct 152 ms 18992 KB Output is correct
10 Correct 158 ms 18644 KB Output is correct
11 Correct 154 ms 18616 KB Output is correct
12 Correct 141 ms 16628 KB Output is correct
13 Correct 175 ms 23912 KB Output is correct
14 Correct 131 ms 13944 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 19064 KB Output is correct
2 Correct 176 ms 16588 KB Output is correct
3 Correct 106 ms 23500 KB Output is correct
4 Correct 146 ms 19032 KB Output is correct
5 Correct 139 ms 18416 KB Output is correct
6 Correct 164 ms 18712 KB Output is correct
7 Correct 143 ms 16600 KB Output is correct
8 Correct 98 ms 23348 KB Output is correct
9 Correct 91 ms 13636 KB Output is correct