Submission #521765

#	Time	Username	Problem	Language	Result	Execution time	Memory
521765		Hamed5001	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	116 ms	20660 KiB

ballmachine

#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 (stderr)

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 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5