oj.uz

Submission #166425

# Submission time Handle Problem Language Result Execution time Memory
166425 2019-12-02T11:13:08 Z dolphingarlic Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 1000 ms 27384 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;
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]});
}

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();
    dfs();

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

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2808 KB Output isn't correct
2 Execution timed out 1073 ms 13724 KB Time limit exceeded
3 Incorrect 102 ms 13816 KB Output isn't correct
4 Execution timed out 1070 ms 2680 KB Time limit exceeded
5 Incorrect 4 ms 2808 KB Output isn't correct
6 Incorrect 5 ms 2808 KB Output isn't correct
7 Execution timed out 1057 ms 2936 KB Time limit exceeded
8 Execution timed out 1078 ms 2808 KB Time limit exceeded
9 Incorrect 13 ms 3448 KB Output isn't correct
10 Execution timed out 1083 ms 5496 KB Time limit exceeded
11 Incorrect 230 ms 14008 KB Output isn't correct
12 Incorrect 122 ms 13848 KB Output isn't correct
13 Incorrect 144 ms 13832 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 7800 KB Output is correct
2 Incorrect 448 ms 23004 KB Output isn't correct
3 Incorrect 111 ms 18676 KB Output isn't correct
4 Execution timed out 1073 ms 9080 KB Time limit exceeded
5 Execution timed out 1091 ms 8568 KB Time limit exceeded
6 Incorrect 194 ms 9208 KB Output isn't correct
7 Incorrect 200 ms 8368 KB Output isn't correct
8 Correct 59 ms 7672 KB Output is correct
9 Incorrect 361 ms 23136 KB Output isn't correct
10 Incorrect 457 ms 22776 KB Output isn't correct
11 Incorrect 367 ms 22776 KB Output isn't correct
12 Incorrect 399 ms 20964 KB Output isn't correct
13 Correct 193 ms 24316 KB Output is correct
14 Incorrect 115 ms 18748 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 140 ms 13024 KB Output isn't correct
2 Incorrect 674 ms 21356 KB Output isn't correct
3 Correct 341 ms 22140 KB Output is correct
4 Incorrect 231 ms 18868 KB Output isn't correct
5 Incorrect 328 ms 18660 KB Output isn't correct
6 Incorrect 315 ms 18820 KB Output isn't correct
7 Incorrect 294 ms 17272 KB Output isn't correct
8 Correct 345 ms 22136 KB Output is correct
9 Incorrect 340 ms 23256 KB Output isn't correct
10 Incorrect 475 ms 22952 KB Output isn't correct
11 Incorrect 520 ms 22980 KB Output isn't correct
12 Incorrect 466 ms 21396 KB Output isn't correct
13 Correct 519 ms 27384 KB Output is correct
14 Incorrect 195 ms 18956 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 398 ms 23240 KB Output isn't correct
2 Incorrect 481 ms 21336 KB Output isn't correct
3 Correct 239 ms 27068 KB Output is correct
4 Incorrect 406 ms 23212 KB Output isn't correct
5 Incorrect 579 ms 22904 KB Output isn't correct
6 Incorrect 413 ms 22868 KB Output isn't correct
7 Incorrect 474 ms 21240 KB Output isn't correct
8 Correct 212 ms 27000 KB Output is correct
9 Incorrect 107 ms 18516 KB Output isn't correct