oj.uz

답안 #30527

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
30527 2017-07-24T12:18:03 Z RezwanArefin01 Ball Machine (BOI13_ballmachine) C++14
7.53968 / 100
 163 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) {
	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); 
	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 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 4756 KB Output isn't correct
2 Incorrect 83 ms 6892 KB Output isn't correct
3 Incorrect 83 ms 6892 KB Output isn't 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 0 ms 4756 KB Output isn't correct
8 Incorrect 0 ms 4756 KB Output isn't correct
9 Incorrect 3 ms 4888 KB Output isn't correct
10 Incorrect 13 ms 5284 KB Output isn't correct
11 Incorrect 93 ms 6892 KB Output isn't correct
12 Incorrect 53 ms 6892 KB Output isn't correct
13 Incorrect 69 ms 6892 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 6656 KB Output is correct
2 Incorrect 83 ms 11056 KB Output isn't correct
3 Incorrect 56 ms 8320 KB Output isn't correct
4 Incorrect 43 ms 6644 KB Output isn't correct
5 Incorrect 39 ms 6512 KB Output isn't correct
6 Incorrect 39 ms 6516 KB Output isn't correct
7 Incorrect 39 ms 6096 KB Output isn't correct
8 Correct 43 ms 6656 KB Output is correct
9 Incorrect 76 ms 11480 KB Output isn't correct
10 Incorrect 79 ms 11060 KB Output isn't correct
11 Incorrect 146 ms 11064 KB Output isn't correct
12 Incorrect 119 ms 9820 KB Output isn't correct
13 Correct 109 ms 13668 KB Output is correct
14 Incorrect 106 ms 8320 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 43 ms 8104 KB Output isn't correct
2 Incorrect 143 ms 9892 KB Output isn't correct
3 Incorrect 96 ms 13020 KB Output isn't correct
4 Incorrect 86 ms 10540 KB Output isn't correct
5 Incorrect 93 ms 10204 KB Output isn't correct
6 Incorrect 93 ms 10212 KB Output isn't correct
7 Incorrect 89 ms 9272 KB Output isn't correct
8 Incorrect 76 ms 13016 KB Output isn't correct
9 Incorrect 109 ms 11480 KB Output isn't correct
10 Incorrect 99 ms 11064 KB Output isn't correct
11 Incorrect 109 ms 11068 KB Output isn't correct
12 Incorrect 133 ms 9888 KB Output isn't correct
13 Incorrect 76 ms 14576 KB Output isn't correct
14 Incorrect 59 ms 8324 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 79 ms 11480 KB Output isn't correct
2 Incorrect 93 ms 9892 KB Output isn't correct
3 Correct 76 ms 14580 KB Output is correct
4 Incorrect 159 ms 11476 KB Output isn't correct
5 Incorrect 86 ms 11064 KB Output isn't correct
6 Incorrect 163 ms 11072 KB Output isn't correct
7 Incorrect 149 ms 9892 KB Output isn't correct
8 Correct 133 ms 14580 KB Output is correct
9 Incorrect 99 ms 8324 KB Output isn't correct