oj.uz

답안 #30525

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
30525 2017-07-24T12:08:14 Z RezwanArefin01 Ball Machine (BOI13_ballmachine) C++14
0 / 100
 1000 ms 17660 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[]) {
	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

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.0

# 결과 실행 시간 메모리 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 99 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 76 ms 9156 KB Output isn't correct
13 Execution timed out 1000 ms 9156 KB Execution timed out

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1000 ms 7060 KB Execution timed out
2 Execution timed out 1000 ms 14136 KB Execution timed out
3 Incorrect 106 ms 11396 KB Output isn't correct
4 Execution timed out 1000 ms 7580 KB Execution timed out
5 Execution timed out 1000 ms 7448 KB Execution timed out
6 Execution timed out 1000 ms 7444 KB Execution timed out
7 Execution timed out 1000 ms 6900 KB Execution timed out
8 Execution timed out 1000 ms 7060 KB Execution timed out
9 Execution timed out 1000 ms 14560 KB Execution timed out
10 Execution timed out 1000 ms 14140 KB Execution timed out
11 Execution timed out 1000 ms 14140 KB Execution timed out
12 Execution timed out 1000 ms 12768 KB Execution timed out
13 Incorrect 153 ms 16220 KB Output isn't correct
14 Incorrect 86 ms 11396 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 46 ms 9572 KB Output isn't correct
2 Incorrect 126 ms 12968 KB Output isn't correct
3 Incorrect 63 ms 15176 KB Output isn't correct
4 Incorrect 83 ms 12696 KB Output isn't correct
5 Incorrect 69 ms 12364 KB Output isn't correct
6 Incorrect 113 ms 12368 KB Output isn't correct
7 Incorrect 89 ms 11432 KB Output isn't correct
8 Incorrect 123 ms 15172 KB Output isn't correct
9 Incorrect 129 ms 14560 KB Output isn't correct
10 Incorrect 143 ms 14144 KB Output isn't correct
11 Incorrect 146 ms 14148 KB Output isn't correct
12 Incorrect 149 ms 12972 KB Output isn't correct
13 Incorrect 169 ms 17656 KB Output isn't correct
14 Incorrect 103 ms 11400 KB Output isn't correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1000 ms 14560 KB Execution timed out
2 Execution timed out 1000 ms 12972 KB Execution timed out
3 Incorrect 163 ms 17660 KB Output isn't correct
4 Execution timed out 1000 ms 14556 KB Execution timed out
5 Execution timed out 1000 ms 14148 KB Execution timed out
6 Execution timed out 1000 ms 14152 KB Execution timed out
7 Execution timed out 1000 ms 12972 KB Execution timed out
8 Incorrect 89 ms 17660 KB Output isn't correct
9 Incorrect 119 ms 11400 KB Output isn't correct