oj.uz

Submission #872042

# Submission time Handle Problem Language Result Execution time Memory
872042 2023-11-12T07:40:26 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 161 ms 30156 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 100'000 + 7, L = 20 + 7;
vector<int> ord, adj[N];
int n, q, r, mn[N], idx[N], sp[L][N];
bool mark[N];
set<int> s;

void read_input() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        int p;
        cin >> p;
        if (p == 0) {
            r = i;
        } else {
            adj[i].push_back(p);
            adj[p].push_back(i);
        }
    }
}

void dfs1(int v, int p) {
    mn[v] = v;
    for (int u : adj[v])
        if (u != p) {
            dfs1(u, v);
            mn[v] = min(mn[v], mn[u]);
        }
}

void dfs2(int v, int p) {
    sort(adj[v].begin(), adj[v].end(), [](int v1, int v2) -> bool { return mn[v1] < mn[v2]; });
    for (int u : adj[v])
        if (u != p)
            dfs2(u, v);
    ord.push_back(v);
}

void dfs3(int v, int p) {
    sp[0][v] = p;
    for (int i = 1; i < L; i++) {
        if (sp[i - 1][sp[i - 1][v]] == 0)
            break;
        else
            sp[i][v] = sp[i - 1][sp[i - 1][v]];
    }

    for (int u : adj[v])
        if (u != p)
            dfs3(u, v);
}

void pre_process() {
    dfs1(r, 0);
    ord.push_back(-1);
    dfs2(r, 0);
    dfs3(r, 0);
    for (int i = 1; i <= n; i++)
        idx[ord[i]] = i;
    for (int i = 1; i <= n; i++)
        s.insert(i);
}

void add(int x) {
    for (int i = 1; i <= x; i++) {
        int t = *s.begin();
        s.erase(t);
        mark[t] = true;
        
        if (i == x)
            cout << ord[t] << '\n';
    }
}

void remove(int v) {
    int res = 0, u = v;
    for (int i = L - 1; i >= 0; i--)
        if (mark[idx[sp[i][u]]]) {
            u = sp[i][u];
            res |= (1 << i);
        }

    mark[idx[u]] = false;
    s.insert(idx[u]);

    cout << res << '\n';
}

void solve() {
    while (q--) {
        int t, x;
        cin >> t >> x;
        if (t == 1)
            add(x);
        else
            remove(x);
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    read_input();
    pre_process();
    solve();
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Correct 73 ms 12572 KB Output is correct
3 Correct 50 ms 12636 KB Output is correct
4 Correct 2 ms 5724 KB Output is correct
5 Correct 1 ms 5724 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 2 ms 5980 KB Output is correct
8 Correct 2 ms 5980 KB Output is correct
9 Correct 5 ms 6236 KB Output is correct
10 Correct 16 ms 7516 KB Output is correct
11 Correct 74 ms 12620 KB Output is correct
12 Correct 48 ms 12532 KB Output is correct
13 Correct 74 ms 12656 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 13776 KB Output is correct
2 Correct 115 ms 25800 KB Output is correct
3 Correct 62 ms 15436 KB Output is correct
4 Correct 46 ms 14604 KB Output is correct
5 Correct 48 ms 14484 KB Output is correct
6 Correct 50 ms 14428 KB Output is correct
7 Correct 44 ms 13580 KB Output is correct
8 Correct 25 ms 13660 KB Output is correct
9 Correct 98 ms 25864 KB Output is correct
10 Correct 148 ms 25812 KB Output is correct
11 Correct 97 ms 25804 KB Output is correct
12 Correct 96 ms 21448 KB Output is correct
13 Correct 80 ms 27592 KB Output is correct
14 Correct 60 ms 15412 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 16852 KB Output is correct
2 Correct 120 ms 21972 KB Output is correct
3 Correct 93 ms 25668 KB Output is correct
4 Correct 77 ms 20940 KB Output is correct
5 Correct 84 ms 20932 KB Output is correct
6 Correct 74 ms 20884 KB Output is correct
7 Correct 85 ms 19384 KB Output is correct
8 Correct 86 ms 25764 KB Output is correct
9 Correct 113 ms 23952 KB Output is correct
10 Correct 118 ms 26068 KB Output is correct
11 Correct 114 ms 26052 KB Output is correct
12 Correct 107 ms 22048 KB Output is correct
13 Correct 138 ms 30156 KB Output is correct
14 Correct 91 ms 15856 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 26060 KB Output is correct
2 Correct 106 ms 21792 KB Output is correct
3 Correct 105 ms 29680 KB Output is correct
4 Correct 119 ms 25988 KB Output is correct
5 Correct 117 ms 25812 KB Output is correct
6 Correct 108 ms 25912 KB Output is correct
7 Correct 161 ms 21952 KB Output is correct
8 Correct 86 ms 29640 KB Output is correct
9 Correct 58 ms 15408 KB Output is correct