Submission #30525

#	Time	Username	Problem	Language	Result	Execution time	Memory
30525		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[]) {
	int n, q, root; 
	scanf("%d %d", &n, &q); 
	for(int i = 1; i <= n; i++) {
		int p; scanf("%d", &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; 
		scanf("%d %d", &c, &x); 
		if(c == 1) {
			node u; 
			while(x--) {
				u = *(Q.begin()); 
				Q.erase(Q.begin()); 
			} printf("%d\n", u.u);
		} else {
			auto it = Q.find({x, prior[x]}); 
			if(it != Q.end()) 
				Q.erase(it);
			puts("0");
		}
	}

}

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:29:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q); 
                        ^
ballmachine.cpp:31:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int p; scanf("%d", &p); 
                         ^
ballmachine.cpp:44:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &c, &x); 
                         ^

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