Submission #521758

#	Time	Username	Problem	Language	Result	Execution time	Memory
521758		Hamed5001	Ball Machine (BOI13_ballmachine)	C++14	0 / 100	99 ms	21396 KiB

ballmachine

#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] = 1e9;
    for (auto it : adj[node]) {
        dfs1(it);
        mnSub[node] = min(mnSub[node], mnSub[it]);
    }
    if (!adj[node].size()) mnSub[node] = node;
}

int idpr = 0;
void dfs2(int node) {
    for (auto it : adj[node]) {
        dfs2(it);
    } 
    priority[node] = idpr++;
}

void init() {
    dfs1(1); 
    for (int i = 1; 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;
    }
	return 0;
}

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);
        }
		if (Q) cout << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40
• Subtask 4: 0 / 5