Submission #30524

#	Time	Username	Problem	Language	Result	Execution time	Memory
30524		RezwanArefin01	Ball Machine (BOI13_ballmachine)	C++14	0 / 100	1000 ms	17660 KiB

ballmachine

//Bismillahir Rahmanir Rahim
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
vector<int> adj[maxn], post; 
int prior[maxn]; 
int MinDfs(int u) {
	if(!adj[u].size()) return u;
	for(int v : adj[u]) 
		prior[v] = MinDfs(v); 
	sort(adj[u].begin(), adj[u].end(), [](int a, int b) { return prior[a] < prior[b]; } ); 
} 
void postDfs(int u) {
	if(!adj[u].size()) { post.push_back(u); return; }
	for(int v : adj[u]) postDfs(v); 
	post.push_back(u);
}

struct node{
	int u, prior; 
	bool operator < (const node &p) const {
		return prior < p.prior; 
	}
};

int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
	freopen("in", "r", stdin);
#endif
	int n, q, root; cin>>n>>q; 
	for(int i = 1; i <= n; i++) {
		int p; cin>>p;
		if(p == 0) root = i;
		adj[p].push_back(i);  
	} 
	MinDfs(root); 
	postDfs(root); 
	set<node> Q; 
	for(int i = 0; i < n; i++) {
		Q.insert({post[i], i});
		prior[post[i]] = i;
	}
	while(q--) {
		int c, x; 
		cin>>c>>x; 
		if(c == 1) {
			node u; 
			while(x--) {
				u = *(Q.begin()); 
				Q.erase(Q.begin()); 
			} cout<<u.u<<endl;
		} else {
			auto it = Q.find({x, prior[x]}); 
			if(it != Q.end()) 
				Q.erase(it);
			cout<<0<<endl;
		}
	}

}

Compilation message (stderr)

ballmachine.cpp: In function 'int MinDfs(int)':
ballmachine.cpp:13:1: warning: control reaches end of non-void function [-Wreturn-type]
 } 
 ^
ballmachine.cpp: In function 'int main(int, const char**)':
ballmachine.cpp:52:14: warning: 'u.node::u' may be used uninitialized in this function [-Wmaybe-uninitialized]
    } cout<<u.u<<endl;
              ^

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