oj.uz

Submission #547254

# Submission time Handle Problem Language Result Execution time Memory
547254 2022-04-10T06:01:46 Z Jomnoi Ball Machine (BOI13_ballmachine) C++17
75.8974 / 100
 1000 ms 22092 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(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(int u) {
    for(auto v : graph[u]) {
        postorder(v);
    }
    timer++;
    st[u] = timer;
    pos[timer] = u;
}

int jump(int u, int k) {
    for(int i = 0; i < 20; i++) {
        if(k & (1<<i)) {
            u = parent[u][i];
        }
    }
    return u;
}

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

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

int query(int idx, int l, 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];
        graph[parent[i][0]].push_back(i);
        if(parent[i][0] == 0) {
            root = 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--;
                    if(k > 0) {
                        idx++;
                    }
                }
            }
            cout << pos[idx] << '\n';
        }
        else {
            int x;
            cin >> x;
            int l = 0, r = depth[x], res;
            while(l <= r) {
                int mid = (l + r) / 2;

                if(state[jump(x, mid)] == true) {
                    res = mid;
                    l = mid + 1;
                }
                else {
                    r = mid - 1;
                }
            }
            cout << res << '\n';
            
            idx = jump(x, res);
            state[idx] = false;
            update(1, 1, N, st[idx], false);
        }
    }
    return 0;
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:132:28: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  132 |             cout << res << '\n';
      |                            ^~~~
ballmachine.cpp:115:33: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  115 |             cout << pos[idx] << '\n';
      |                                 ^~~~

Subtask #1
19.2307692308 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 102 ms 11336 KB Output is correct
3 Correct 55 ms 11200 KB Output is correct
4 Execution timed out 1086 ms 2772 KB Time limit exceeded
5 Correct 3 ms 2644 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Execution timed out 1071 ms 2772 KB Time limit exceeded
8 Correct 3 ms 2812 KB Output is correct
9 Correct 7 ms 3196 KB Output is correct
10 Correct 21 ms 4740 KB Output is correct
11 Correct 94 ms 11300 KB Output is correct
12 Correct 56 ms 11196 KB Output is correct
13 Execution timed out 1059 ms 10572 KB Time limit exceeded

Subtask #2
15.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 6604 KB Output is correct
2 Incorrect 232 ms 18072 KB Output isn't correct
3 Correct 79 ms 14572 KB Output is correct
4 Correct 73 ms 7856 KB Output is correct
5 Incorrect 108 ms 7852 KB Output isn't correct
6 Execution timed out 1066 ms 7124 KB Time limit exceeded
7 Incorrect 83 ms 7116 KB Output isn't correct
8 Correct 47 ms 6568 KB Output is correct
9 Correct 162 ms 18540 KB Output is correct
10 Incorrect 207 ms 18224 KB Output isn't correct
11 Execution timed out 1074 ms 17212 KB Time limit exceeded
12 Incorrect 193 ms 16640 KB Output isn't correct
13 Correct 102 ms 19356 KB Output is correct
14 Correct 74 ms 14572 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 10700 KB Output is correct
2 Correct 326 ms 17340 KB Output is correct
3 Correct 206 ms 17912 KB Output is correct
4 Correct 135 ms 15336 KB Output is correct
5 Correct 179 ms 14972 KB Output is correct
6 Correct 173 ms 15032 KB Output is correct
7 Correct 141 ms 14216 KB Output is correct
8 Correct 225 ms 17868 KB Output is correct
9 Correct 219 ms 18932 KB Output is correct
10 Correct 394 ms 18388 KB Output is correct
11 Correct 273 ms 18420 KB Output is correct
12 Correct 300 ms 17216 KB Output is correct
13 Correct 364 ms 22092 KB Output is correct
14 Correct 117 ms 15240 KB Output is correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 336 ms 18760 KB Output isn't correct
2 Incorrect 257 ms 17236 KB Output isn't correct
3 Correct 146 ms 21380 KB Output is correct
4 Incorrect 257 ms 18832 KB Output isn't correct
5 Incorrect 301 ms 18316 KB Output isn't correct
6 Execution timed out 1074 ms 17224 KB Time limit exceeded
7 Incorrect 224 ms 17192 KB Output isn't correct
8 Correct 106 ms 21384 KB Output is correct
9 Correct 74 ms 14568 KB Output is correct