oj.uz

Submission #521765

# Submission time Handle Problem Language Result Execution time Memory
521765 2022-02-03T02:38:36 Z Hamed5001 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 116 ms 20660 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int mxN = 1e5 + 1, LOG = 20;
int N, Q, root;
int priority[mxN], mnSub[mxN], parentBL[mxN][LOG];
bool hasBall[mxN];
vector<int> adj[mxN];
priority_queue<pair<int, int>> emp;
 
void dfs1(int node) {
    mnSub[node] = node;
    for (auto it : adj[node]) {
        dfs1(it);
        mnSub[node] = min(mnSub[node], mnSub[it]);
    }
}
 
int idpr = 0;
void dfs2(int node) {
    for (auto it : adj[node]) {
        dfs2(it);
    } 
    priority[node] = idpr++;
}
 
void init() {
    dfs1(0); 
    for (int i = 0; i <= N; ++i) {
        sort(adj[i].begin(), adj[i].end(), [](int node1, int node2){
            return mnSub[node1] < mnSub[node2];
        });
    }
    dfs2(0);
    for (int i = 1; i <= N; ++i) emp.push({N - priority[i], i});
    
    for (int i = 1; i < LOG; ++i)
        for (int j = 1; j <= N; ++j)
            parentBL[j][i] = parentBL[parentBL[j][i-1]][i-1];
}
 
int inser(int x) {
    for (int i = 0; i < x; ++i) {
        int curr = emp.top().second;
        hasBall[curr] = 1;
        emp.pop();
        if (i + 1 == x) return curr;
    }
}
 
int rem(int x) {
    int u = x, k = 0;
    for (int i = LOG - 1; i >= 0; --i) {
        if (hasBall[parentBL[u][i]]) {
            k |= (1 << i);
            u = parentBL[u][i];
        }
    } 
    hasBall[u] = 0;
    emp.push({N - priority[u], u});
    return k;
}
 
void solve() {
    cin >> N >> Q;
    for (int i = 1; i <= N; ++i) {
        cin >> parentBL[i][0];
        adj[parentBL[i][0]].push_back(i);
    }
    
    init();
    
    while(Q--) {
        int k, x;
        cin >> k >> x;
        if (k == 1) {
            cout << inser(x);
        }
        else {
            cout << rem(x);
        }
        cout << '\n';
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

Compilation message

ballmachine.cpp: In function 'int inser(int)':
ballmachine.cpp:49:1: warning: control reaches end of non-void function [-Wreturn-type]
   49 | }
      | ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 63 ms 10168 KB Output is correct
3 Correct 44 ms 10356 KB Output is correct
4 Correct 2 ms 2636 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2764 KB Output is correct
7 Correct 2 ms 2764 KB Output is correct
8 Correct 2 ms 2764 KB Output is correct
9 Correct 5 ms 3148 KB Output is correct
10 Correct 14 ms 4544 KB Output is correct
11 Correct 61 ms 10232 KB Output is correct
12 Correct 43 ms 10356 KB Output is correct
13 Correct 54 ms 10172 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6232 KB Output is correct
2 Correct 109 ms 16804 KB Output is correct
3 Correct 56 ms 13908 KB Output is correct
4 Correct 38 ms 7212 KB Output is correct
5 Correct 38 ms 6984 KB Output is correct
6 Correct 36 ms 7104 KB Output is correct
7 Correct 37 ms 6348 KB Output is correct
8 Correct 25 ms 6136 KB Output is correct
9 Correct 88 ms 17168 KB Output is correct
10 Correct 88 ms 16744 KB Output is correct
11 Correct 80 ms 16716 KB Output is correct
12 Correct 90 ms 15300 KB Output is correct
13 Correct 68 ms 18288 KB Output is correct
14 Correct 57 ms 13880 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 10060 KB Output is correct
2 Correct 92 ms 15756 KB Output is correct
3 Correct 76 ms 16904 KB Output is correct
4 Correct 67 ms 14396 KB Output is correct
5 Correct 64 ms 14144 KB Output is correct
6 Correct 62 ms 14104 KB Output is correct
7 Correct 61 ms 13120 KB Output is correct
8 Correct 73 ms 16972 KB Output is correct
9 Correct 100 ms 17268 KB Output is correct
10 Correct 97 ms 16828 KB Output is correct
11 Correct 99 ms 16848 KB Output is correct
12 Correct 93 ms 15668 KB Output is correct
13 Correct 116 ms 20660 KB Output is correct
14 Correct 78 ms 13908 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 17428 KB Output is correct
2 Correct 100 ms 15864 KB Output is correct
3 Correct 87 ms 20292 KB Output is correct
4 Correct 103 ms 17416 KB Output is correct
5 Correct 95 ms 16876 KB Output is correct
6 Correct 83 ms 16876 KB Output is correct
7 Correct 97 ms 15692 KB Output is correct
8 Correct 75 ms 20404 KB Output is correct
9 Correct 56 ms 13884 KB Output is correct