Submission #30528

#	Time	Username	Problem	Language	Result	Execution time	Memory
30528		RezwanArefin01	Ball Machine (BOI13_ballmachine)	C++14	35.51 / 100	149 ms	14580 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) {
	prior[u] = u; 
	for(int v : adj[u]) {
		prior[u] = min(prior[u], MinDfs(v)); 
	}
	sort(adj[u].begin(), adj[u].end(), [](int &a, int &b) { return prior[a] < prior[b]; } ); 
	return prior[u];
} 
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; 
	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); 
	priority_queue<node> Q; 
	for(int i = 0; i < n; i++) {
		Q.push({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.top();
				Q.pop();  
			} printf("%d\n", u.u);
		} else {
			Q.push({x, prior[x]}); 
			puts("0");
		}
	}

}

Compilation message (stderr)

ballmachine.cpp: In function 'int main(int, const char**)':
ballmachine.cpp:34: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:36: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:49:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &c, &x); 
                         ^
ballmachine.cpp:41:15: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  postDfs(root); 
               ^

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