oj.uz

Submission #30528

# Submission time Handle Problem Language Result Execution time Memory
30528 2017-07-24T12:22:27 Z RezwanArefin01 Ball Machine (BOI13_ballmachine) C++14
35.5128 / 100
 149 ms 14580 KB 
//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

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.84615384615 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 4756 KB Output isn't correct
2 Incorrect 56 ms 6892 KB Output isn't correct
3 Correct 73 ms 6892 KB Output is correct
4 Incorrect 0 ms 4756 KB Output isn't correct
5 Incorrect 0 ms 4756 KB Output isn't correct
6 Incorrect 0 ms 4756 KB Output isn't correct
7 Incorrect 3 ms 4756 KB Output isn't correct
8 Incorrect 0 ms 4756 KB Output isn't correct
9 Incorrect 6 ms 4888 KB Output isn't correct
10 Incorrect 13 ms 5284 KB Output isn't correct
11 Incorrect 79 ms 6892 KB Output isn't correct
12 Correct 53 ms 6892 KB Output is correct
13 Incorrect 53 ms 6892 KB Output isn't correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 6660 KB Output is correct
2 Correct 133 ms 11060 KB Output is correct
3 Correct 73 ms 8320 KB Output is correct
4 Correct 56 ms 6644 KB Output is correct
5 Correct 39 ms 6516 KB Output is correct
6 Correct 39 ms 6512 KB Output is correct
7 Correct 39 ms 6096 KB Output is correct
8 Correct 39 ms 6656 KB Output is correct
9 Correct 133 ms 11484 KB Output is correct
10 Correct 126 ms 11060 KB Output is correct
11 Correct 133 ms 11064 KB Output is correct
12 Correct 116 ms 9820 KB Output is correct
13 Correct 116 ms 13668 KB Output is correct
14 Correct 89 ms 8320 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 8104 KB Output isn't correct
2 Incorrect 126 ms 9888 KB Output isn't correct
3 Incorrect 93 ms 13016 KB Output isn't correct
4 Incorrect 79 ms 10544 KB Output isn't correct
5 Incorrect 73 ms 10208 KB Output isn't correct
6 Incorrect 79 ms 10208 KB Output isn't correct
7 Incorrect 79 ms 9276 KB Output isn't correct
8 Incorrect 113 ms 13016 KB Output isn't correct
9 Incorrect 129 ms 11488 KB Output isn't correct
10 Incorrect 109 ms 11068 KB Output isn't correct
11 Incorrect 123 ms 11068 KB Output isn't correct
12 Incorrect 126 ms 9896 KB Output isn't correct
13 Incorrect 149 ms 14580 KB Output isn't correct
14 Incorrect 76 ms 8324 KB Output isn't correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 119 ms 11476 KB Output isn't correct
2 Incorrect 136 ms 9892 KB Output isn't correct
3 Correct 139 ms 14576 KB Output is correct
4 Incorrect 103 ms 11476 KB Output isn't correct
5 Incorrect 116 ms 11064 KB Output isn't correct
6 Incorrect 116 ms 11072 KB Output isn't correct
7 Incorrect 113 ms 9892 KB Output isn't correct
8 Correct 126 ms 14576 KB Output is correct
9 Correct 96 ms 8324 KB Output is correct