oj.uz

Submission #521761

# Submission time Handle Problem Language Result Execution time Memory
521761 2022-02-03T02:01:28 Z Hamed5001 Ball Machine (BOI13_ballmachine) C++14
0 / 100
 105 ms 19088 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int mxN = 1e5 + 1, LOG = 20;
int N, Q;
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(1); 
    for (int i = 0; i <= N; ++i) {
        sort(adj[i].begin(), adj[i].end(), [](int node1, int node2){
            return mnSub[node1] < mnSub[node2];
        });
    }
    dfs2(1);
    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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2636 KB Output isn't correct
2 Incorrect 58 ms 9704 KB Output isn't correct
3 Incorrect 44 ms 10044 KB Output isn't correct
4 Incorrect 1 ms 2636 KB Output isn't correct
5 Incorrect 2 ms 2636 KB Output isn't correct
6 Incorrect 2 ms 2764 KB Output isn't correct
7 Incorrect 2 ms 2764 KB Output isn't correct
8 Incorrect 2 ms 2764 KB Output isn't correct
9 Incorrect 5 ms 3036 KB Output isn't correct
10 Incorrect 12 ms 4428 KB Output isn't correct
11 Incorrect 58 ms 9852 KB Output isn't correct
12 Incorrect 42 ms 9916 KB Output isn't correct
13 Incorrect 52 ms 9632 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 6320 KB Output isn't correct
2 Incorrect 103 ms 15548 KB Output isn't correct
3 Incorrect 53 ms 13280 KB Output isn't correct
4 Incorrect 39 ms 6308 KB Output isn't correct
5 Incorrect 39 ms 6216 KB Output isn't correct
6 Incorrect 41 ms 6268 KB Output isn't correct
7 Incorrect 40 ms 5944 KB Output isn't correct
8 Incorrect 26 ms 6304 KB Output isn't correct
9 Incorrect 81 ms 17148 KB Output isn't correct
10 Incorrect 105 ms 15500 KB Output isn't correct
11 Incorrect 75 ms 13884 KB Output isn't correct
12 Incorrect 74 ms 13408 KB Output isn't correct
13 Incorrect 57 ms 15264 KB Output isn't correct
14 Incorrect 53 ms 13268 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 9788 KB Output isn't correct
2 Incorrect 86 ms 15288 KB Output isn't correct
3 Incorrect 61 ms 14156 KB Output isn't correct
4 Incorrect 50 ms 11972 KB Output isn't correct
5 Incorrect 58 ms 11592 KB Output isn't correct
6 Incorrect 49 ms 11676 KB Output isn't correct
7 Incorrect 55 ms 12956 KB Output isn't correct
8 Incorrect 67 ms 14164 KB Output isn't correct
9 Incorrect 78 ms 14144 KB Output isn't correct
10 Incorrect 88 ms 13844 KB Output isn't correct
11 Incorrect 89 ms 14908 KB Output isn't correct
12 Incorrect 85 ms 15276 KB Output isn't correct
13 Incorrect 98 ms 16764 KB Output isn't correct
14 Incorrect 71 ms 13184 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 90 ms 14216 KB Output isn't correct
2 Incorrect 88 ms 15596 KB Output isn't correct
3 Incorrect 76 ms 19088 KB Output isn't correct
4 Incorrect 89 ms 14220 KB Output isn't correct
5 Incorrect 82 ms 13744 KB Output isn't correct
6 Incorrect 84 ms 16244 KB Output isn't correct
7 Incorrect 86 ms 15568 KB Output isn't correct
8 Incorrect 71 ms 19012 KB Output isn't correct
9 Incorrect 56 ms 13316 KB Output isn't correct