oj.uz

Submission #166426

# Submission time Handle Problem Language Result Execution time Memory
166426 2019-12-02T11:16:08 Z dolphingarlic Ball Machine (BOI13_ballmachine) C++14
100 / 100
 318 ms 27188 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

struct Node {
    int id, order;
};
bool operator<(Node A, Node B) {
    return A.order < B.order;
}

vector<int> graph[100001];
int ancestor[100001][20], least_child[100001], order[100001], cnt = 1;
bool emp[100001];
set<Node> no_ball;

bool cmp(int A, int B) {
    return least_child[A] < least_child[B];
}

void find_least_children(int node = 0) {
    least_child[node] = node;
    FOR(i, 1, 20) {
        if (!ancestor[node][i - 1]) break;
        ancestor[node][i] = ancestor[ancestor[node][i - 1]][i - 1];
    }

    for (int i : graph[node]) {
        ancestor[i][0] = node;
        find_least_children(i);
        least_child[node] = min(least_child[node], least_child[i]);
    }
}

void dfs(int node = 0) {
    for (int i : graph[node]) dfs(i);
    order[node] = cnt++;
    if (node) no_ball.insert({node, order[node]});
    emp[node] = true;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    FOR(i, 1, n + 1) {
        int p;
        cin >> p;
        graph[p].push_back(i);
    }
    find_least_children();
    FOR(i, 1, n + 1) sort(graph[i].begin(), graph[i].end(), cmp);
    dfs();

    while (q--) {
        int t, x;
        cin >> t >> x;
        if (t == 1) {
            FOR(i, 1, x) {
                emp[(*no_ball.begin()).id] = false;
                no_ball.erase(no_ball.begin());
            }
            cout << (*no_ball.begin()).id << '\n';
            emp[(*no_ball.begin()).id] = false;
            no_ball.erase(no_ball.begin());
        } else {
            int lca = x, ans = 0;
            for (int i = 19; ~i; i--) {
                if (ancestor[lca][i] && !emp[ancestor[lca][i]]) {
                    ans += (1<<i);
                    lca = ancestor[lca][i];
                }
            }
            emp[lca] = true;
            no_ball.insert({lca, order[lca]});
            cout << ans << '\n';
        }
    }
    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2808 KB Output is correct
2 Correct 132 ms 12792 KB Output is correct
3 Correct 84 ms 12920 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2936 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 10 ms 3340 KB Output is correct
10 Correct 26 ms 5240 KB Output is correct
11 Correct 152 ms 12760 KB Output is correct
12 Correct 83 ms 12920 KB Output is correct
13 Correct 114 ms 12796 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 7160 KB Output is correct
2 Correct 194 ms 21468 KB Output is correct
3 Correct 112 ms 17652 KB Output is correct
4 Correct 75 ms 8668 KB Output is correct
5 Correct 76 ms 8824 KB Output is correct
6 Correct 68 ms 8380 KB Output is correct
7 Correct 71 ms 7544 KB Output is correct
8 Correct 44 ms 7160 KB Output is correct
9 Correct 166 ms 21880 KB Output is correct
10 Correct 191 ms 21792 KB Output is correct
11 Correct 168 ms 22068 KB Output is correct
12 Correct 200 ms 20028 KB Output is correct
13 Correct 136 ms 23596 KB Output is correct
14 Correct 106 ms 17816 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 12920 KB Output is correct
2 Correct 217 ms 20728 KB Output is correct
3 Correct 154 ms 21624 KB Output is correct
4 Correct 149 ms 18424 KB Output is correct
5 Correct 148 ms 18040 KB Output is correct
6 Correct 156 ms 18092 KB Output is correct
7 Correct 139 ms 16632 KB Output is correct
8 Correct 154 ms 21588 KB Output is correct
9 Correct 210 ms 22648 KB Output is correct
10 Correct 226 ms 22236 KB Output is correct
11 Correct 227 ms 22008 KB Output is correct
12 Correct 206 ms 20472 KB Output is correct
13 Correct 218 ms 26744 KB Output is correct
14 Correct 173 ms 18548 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 23236 KB Output is correct
2 Correct 211 ms 20608 KB Output is correct
3 Correct 159 ms 27000 KB Output is correct
4 Correct 205 ms 23416 KB Output is correct
5 Correct 209 ms 22620 KB Output is correct
6 Correct 186 ms 22896 KB Output is correct
7 Correct 211 ms 21344 KB Output is correct
8 Correct 296 ms 27188 KB Output is correct
9 Correct 119 ms 18696 KB Output is correct