oj.uz

Submission #593767

# Submission time Handle Problem Language Result Execution time Memory
593767 2022-07-11T14:56:33 Z bogdanvladmihai Ball Machine (BOI13_ballmachine) C++14
100 / 100
 130 ms 31812 KB 
#include <bits/stdc++.h>
using namespace std;

/***
Given a rooted tree, you have to support 2 types of operations:
* paint the root of a full black subtree in black
* check where the path from a black node to the root becomes white

I can do the erases using binary lifting:
* if the 2^k ancestor of node u is black, than all the nodes between them are black
* if not, you can go down the tree

Add operation:
* I will always want to add in the same exact order
* So I will have a vector of 1 and 0, and I want to find the LAST 0

***/

const int LG = 17;
const int MAXN = 1000 * 100;

vector<int> g[MAXN + 1], order[MAXN + 1];
int dad[MAXN + 1], minValue[MAXN + 1], who[MAXN + 1], tin[MAXN + 1];
int ancestor[LG + 1][MAXN + 1];
bool black[MAXN + 1];
priority_queue<int> fr;

void dfs(int u) {
    vector<pair<int, int>> children;

    for (const int &v : g[u]) {
        dfs(v);

        minValue[u] = min(minValue[u], minValue[v]);
        children.emplace_back(minValue[v], v);
    }

    sort(children.begin(), children.end());
    reverse(children.begin(), children.end());

    for (const auto &p : children) {
        order[u].push_back(p.second);
    }
}

void dfsOrder(int u) {
    static int t = 0;

    tin[u] = t++;
    who[t - 1] = u;

    for (const int &v : order[u]) {
        dfsOrder(v);
    }
}

int add() {
    int u = who[fr.top()];
    fr.pop();

    black[u] = true;
    return u;
}

int erase(int u) {
    int ans = 0;
    for (int l = LG; l >= 0; l--) {
        if (black[ancestor[l][u]]) {
            u = ancestor[l][u];
            ans += (1 << l);
        }
    }

    fr.push(tin[u]);
    black[u] = false;
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n, q; cin >> n >> q;

    int root = -1;
    for (int i = 1; i <= n; i++) {
        cin >> dad[i];

        if (dad[i] != 0) {
            g[dad[i]].push_back(i);
        } else {
            root = i;
        }
    }

    for (int i = 1; i <= n; i++) {
        minValue[i] = i;
        fr.push(i - 1);
    }

    dfs(root);
    dfsOrder(root);

    for (int u = 1; u <= n; u++) {
        ancestor[0][u] = dad[u];
    }

    for (int k = 1; k <= LG; k++) {
        for (int u = 1; u <= n; u++) {
            ancestor[k][u] = ancestor[k - 1][ancestor[k - 1][u]];
        }
    }

    for (int i = 0; i < q; i++) {
        int op, k; cin >> op >> k;

        if (op == 1) {
            int u = -1;
            for (int j = 0; j < k; j++) {
                u = add();
            }

            cout << u << "\n";
        } else {
            cout << erase(k) << "\n";
        }
    }

    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 73 ms 13292 KB Output is correct
3 Correct 48 ms 13380 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 2 ms 5076 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 6 ms 5588 KB Output is correct
10 Correct 15 ms 7136 KB Output is correct
11 Correct 101 ms 13284 KB Output is correct
12 Correct 48 ms 13380 KB Output is correct
13 Correct 64 ms 13320 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 10164 KB Output is correct
2 Correct 101 ms 23672 KB Output is correct
3 Correct 68 ms 17108 KB Output is correct
4 Correct 43 ms 10968 KB Output is correct
5 Correct 39 ms 10724 KB Output is correct
6 Correct 41 ms 10804 KB Output is correct
7 Correct 40 ms 9548 KB Output is correct
8 Correct 27 ms 10160 KB Output is correct
9 Correct 130 ms 24444 KB Output is correct
10 Correct 99 ms 23680 KB Output is correct
11 Correct 84 ms 23628 KB Output is correct
12 Correct 93 ms 20616 KB Output is correct
13 Correct 70 ms 28568 KB Output is correct
14 Correct 58 ms 17144 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 14852 KB Output is correct
2 Correct 128 ms 21068 KB Output is correct
3 Correct 108 ms 26396 KB Output is correct
4 Correct 78 ms 20700 KB Output is correct
5 Correct 67 ms 20112 KB Output is correct
6 Correct 72 ms 20028 KB Output is correct
7 Correct 70 ms 17844 KB Output is correct
8 Correct 93 ms 26412 KB Output is correct
9 Correct 108 ms 24648 KB Output is correct
10 Correct 126 ms 23772 KB Output is correct
11 Correct 127 ms 23876 KB Output is correct
12 Correct 120 ms 21016 KB Output is correct
13 Correct 130 ms 31812 KB Output is correct
14 Correct 105 ms 17256 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 24760 KB Output is correct
2 Correct 105 ms 21104 KB Output is correct
3 Correct 78 ms 31624 KB Output is correct
4 Correct 125 ms 24820 KB Output is correct
5 Correct 119 ms 23776 KB Output is correct
6 Correct 103 ms 23732 KB Output is correct
7 Correct 106 ms 21016 KB Output is correct
8 Correct 79 ms 31596 KB Output is correct
9 Correct 66 ms 17116 KB Output is correct