oj.uz

Submission #643455

# Submission time Handle Problem Language Result Execution time Memory
643455 2022-09-22T04:29:56 Z makanhulia Ball Machine (BOI13_ballmachine) C++17
100 / 100
 155 ms 24188 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5;
const int LOG = 18;
vector<int>adj[N + 2];
bool mark[N + 2];
int n, q, root;
int p[N + 2], mini[N + 2], in[N + 2], depth[N + 2], t[N + 2];
int up[N + 2][LOG];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>pq;
int timer = 1;

bool byMin(int &a, int &b){
    return mini[a] < mini[b];
}

void dfs(int cur, int d){
    depth[cur] = d;
    up[cur][0] = p[cur];
    for(int i = 1; i < LOG; i++){
        up[cur][i] = up[up[cur][i - 1]][i - 1];
    }

    for(auto &nxt: adj[cur]){
        dfs(nxt, d + 1);
    }

    t[cur] = timer;
    pq.emplace(timer++, cur);
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;

    for(int i = 1; i <= n; i++){
        cin >> p[i];
        if(p[i] == 0) root = i;
        adj[p[i]].push_back(i);
        in[p[i]]++;
    }

    queue<int>leaf;
    for(int i = 1; i <= n; i++){
        mini[i] = i;
        if(!in[i]) leaf.push(i);
    }

    while(!leaf.empty()){
        int cur = leaf.front(); leaf.pop();
        int nxt = p[cur];
        mini[nxt] = min(mini[cur], mini[nxt]); 
        in[nxt]--;
        if(!in[nxt]) leaf.push(nxt);
    }

    for(int i = 1; i <= n; i++){
        if(!adj[i].empty()) sort(adj[i].begin(), adj[i].end(), byMin);
    }

    dfs(root, 0);

    while(q--){
        int a, x; cin >> a >> x;
        if(a == 1){
            for(int i = 0; i < x; i++){
                if(i + 1 == x) cout << pq.top().second << '\n';
                mark[pq.top().second] = true;
                pq.pop();
            }
        } else{
            int tmp = x;
            for(int i = LOG - 1; i >= 0; i--){
                if(mark[up[tmp][i]]) tmp = up[tmp][i];
            }

            mark[tmp] = false;
            pq.emplace(t[tmp], tmp);
            cout << depth[x] - depth[tmp] << '\n';
        }
    }

    return 0;
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 74 ms 10564 KB Output is correct
3 Correct 55 ms 10696 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 3 ms 2772 KB Output is correct
7 Correct 2 ms 2772 KB Output is correct
8 Correct 3 ms 2772 KB Output is correct
9 Correct 6 ms 3156 KB Output is correct
10 Correct 15 ms 4692 KB Output is correct
11 Correct 81 ms 10684 KB Output is correct
12 Correct 52 ms 10728 KB Output is correct
13 Correct 68 ms 10584 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6868 KB Output is correct
2 Correct 138 ms 18668 KB Output is correct
3 Correct 64 ms 14404 KB Output is correct
4 Correct 52 ms 7864 KB Output is correct
5 Correct 49 ms 7632 KB Output is correct
6 Correct 44 ms 7632 KB Output is correct
7 Correct 44 ms 6772 KB Output is correct
8 Correct 28 ms 6884 KB Output is correct
9 Correct 147 ms 19280 KB Output is correct
10 Correct 127 ms 18668 KB Output is correct
11 Correct 108 ms 18796 KB Output is correct
12 Correct 117 ms 16616 KB Output is correct
13 Correct 100 ms 21488 KB Output is correct
14 Correct 66 ms 14324 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 11096 KB Output is correct
2 Correct 133 ms 17004 KB Output is correct
3 Correct 103 ms 19800 KB Output is correct
4 Correct 92 ms 16260 KB Output is correct
5 Correct 103 ms 15688 KB Output is correct
6 Correct 95 ms 15684 KB Output is correct
7 Correct 106 ms 14204 KB Output is correct
8 Correct 98 ms 19808 KB Output is correct
9 Correct 123 ms 19364 KB Output is correct
10 Correct 134 ms 18892 KB Output is correct
11 Correct 137 ms 18992 KB Output is correct
12 Correct 132 ms 16908 KB Output is correct
13 Correct 145 ms 24188 KB Output is correct
14 Correct 106 ms 14468 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 19480 KB Output is correct
2 Correct 118 ms 16928 KB Output is correct
3 Correct 91 ms 23872 KB Output is correct
4 Correct 117 ms 19436 KB Output is correct
5 Correct 155 ms 18948 KB Output is correct
6 Correct 131 ms 18840 KB Output is correct
7 Correct 131 ms 16924 KB Output is correct
8 Correct 98 ms 23880 KB Output is correct
9 Correct 74 ms 14364 KB Output is correct