oj.uz

Submission #643448

# Submission time Handle Problem Language Result Execution time Memory
643448 2022-09-22T04:02:59 Z devariaota Ball Machine (BOI13_ballmachine) C++17
16.1111 / 100
 142 ms 25056 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++){
        if(in[p[i]]) continue;
        mini[i] = i;

        leaf.push(i);
    }

    while(!leaf.empty()){
        int cur = leaf.front(); leaf.pop();
        int nxt = p[cur];
        mini[nxt] = min(cur, 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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Incorrect 93 ms 10972 KB Output isn't correct
3 Incorrect 67 ms 11208 KB Output isn't correct
4 Incorrect 2 ms 2644 KB Output isn't correct
5 Incorrect 3 ms 2672 KB Output isn't correct
6 Incorrect 2 ms 2772 KB Output isn't correct
7 Incorrect 2 ms 2772 KB Output isn't correct
8 Incorrect 2 ms 2816 KB Output isn't correct
9 Incorrect 6 ms 3204 KB Output isn't correct
10 Incorrect 16 ms 4820 KB Output isn't correct
11 Incorrect 79 ms 11028 KB Output isn't correct
12 Incorrect 53 ms 11220 KB Output isn't correct
13 Incorrect 74 ms 11036 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7260 KB Output is correct
2 Incorrect 131 ms 19656 KB Output isn't correct
3 Incorrect 70 ms 15040 KB Output isn't correct
4 Incorrect 57 ms 8440 KB Output isn't correct
5 Incorrect 50 ms 8332 KB Output isn't correct
6 Incorrect 46 ms 8268 KB Output isn't correct
7 Incorrect 48 ms 7424 KB Output isn't correct
8 Correct 34 ms 7348 KB Output is correct
9 Incorrect 120 ms 20016 KB Output isn't correct
10 Incorrect 117 ms 19648 KB Output isn't correct
11 Incorrect 119 ms 19752 KB Output isn't correct
12 Incorrect 118 ms 17392 KB Output isn't correct
13 Correct 83 ms 22208 KB Output is correct
14 Incorrect 64 ms 15024 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 11524 KB Output isn't correct
2 Incorrect 139 ms 17912 KB Output isn't correct
3 Correct 96 ms 20384 KB Output is correct
4 Incorrect 78 ms 16480 KB Output isn't correct
5 Incorrect 83 ms 16228 KB Output isn't correct
6 Incorrect 85 ms 16228 KB Output isn't correct
7 Incorrect 104 ms 14676 KB Output isn't correct
8 Correct 90 ms 20428 KB Output is correct
9 Incorrect 113 ms 20244 KB Output isn't correct
10 Incorrect 130 ms 19776 KB Output isn't correct
11 Incorrect 125 ms 19780 KB Output isn't correct
12 Incorrect 120 ms 17788 KB Output isn't correct
13 Correct 142 ms 25056 KB Output is correct
14 Incorrect 89 ms 15296 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 20172 KB Output isn't correct
2 Incorrect 133 ms 17888 KB Output isn't correct
3 Correct 95 ms 24672 KB Output is correct
4 Incorrect 117 ms 20204 KB Output isn't correct
5 Incorrect 122 ms 19672 KB Output isn't correct
6 Incorrect 108 ms 19756 KB Output isn't correct
7 Incorrect 139 ms 17820 KB Output isn't correct
8 Correct 87 ms 24692 KB Output is correct
9 Incorrect 63 ms 15036 KB Output isn't correct