oj.uz

Submission #30526

# Submission time Handle Problem Language Result Execution time Memory
30526 2017-07-24T12:10:12 Z RezwanArefin01 Ball Machine (BOI13_ballmachine) C++14
7.53968 / 100
 1000 ms 17664 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) {
	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; 
	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 {
			Q.insert({x, prior[x]}); 
			puts("0");
		}
	}

}

Compilation message

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:32: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:34: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:47: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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 4760 KB Execution timed out
2 Execution timed out 1000 ms 9156 KB Execution timed out
3 Incorrect 59 ms 9156 KB Output isn't correct
4 Execution timed out 1000 ms 4760 KB Execution timed out
5 Execution timed out 1000 ms 4760 KB Execution timed out
6 Incorrect 0 ms 4892 KB Output isn't correct
7 Execution timed out 1000 ms 4892 KB Execution timed out
8 Execution timed out 1000 ms 4892 KB Execution timed out
9 Execution timed out 1000 ms 5024 KB Execution timed out
10 Execution timed out 1000 ms 5816 KB Execution timed out
11 Execution timed out 1000 ms 9156 KB Execution timed out
12 Incorrect 86 ms 9156 KB Output isn't correct
13 Incorrect 73 ms 9156 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7064 KB Output is correct
2 Incorrect 166 ms 14136 KB Output isn't correct
3 Incorrect 119 ms 11396 KB Output isn't correct
4 Execution timed out 1000 ms 7576 KB Execution timed out
5 Execution timed out 1000 ms 7444 KB Execution timed out
6 Incorrect 46 ms 7448 KB Output isn't correct
7 Execution timed out 1000 ms 6896 KB Execution timed out
8 Correct 36 ms 7064 KB Output is correct
9 Incorrect 136 ms 14560 KB Output isn't correct
10 Incorrect 186 ms 14144 KB Output isn't correct
11 Incorrect 156 ms 14140 KB Output isn't correct
12 Incorrect 183 ms 12768 KB Output isn't correct
13 Correct 119 ms 16212 KB Output is correct
14 Incorrect 109 ms 11396 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 9576 KB Output isn't correct
2 Incorrect 166 ms 12968 KB Output isn't correct
3 Incorrect 146 ms 15172 KB Output isn't correct
4 Incorrect 133 ms 12696 KB Output isn't correct
5 Incorrect 133 ms 12364 KB Output isn't correct
6 Incorrect 126 ms 12368 KB Output isn't correct
7 Incorrect 129 ms 11428 KB Output isn't correct
8 Incorrect 136 ms 15176 KB Output isn't correct
9 Incorrect 199 ms 14560 KB Output isn't correct
10 Incorrect 219 ms 14148 KB Output isn't correct
11 Incorrect 156 ms 14152 KB Output isn't correct
12 Incorrect 119 ms 12972 KB Output isn't correct
13 Incorrect 189 ms 17664 KB Output isn't correct
14 Incorrect 199 ms 11400 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1000 ms 14564 KB Execution timed out
2 Incorrect 176 ms 12968 KB Output isn't correct
3 Correct 163 ms 17664 KB Output is correct
4 Execution timed out 1000 ms 14564 KB Execution timed out
5 Incorrect 193 ms 14148 KB Output isn't correct
6 Incorrect 146 ms 14148 KB Output isn't correct
7 Incorrect 233 ms 12968 KB Output isn't correct
8 Correct 166 ms 17656 KB Output is correct
9 Incorrect 106 ms 11400 KB Output isn't correct