oj.uz

답안 #30529

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
30529 2017-07-24T12:35:03 Z RezwanArefin01 Ball Machine (BOI13_ballmachine) C++14
59.8657 / 100
 486 ms 22100 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], dep[maxn], par[maxn][18];
bool has[maxn]; 
int MinDfs(int u) {
	prior[u] = u; 
	for(int v : adj[u]) {
		dep[v] = dep[u] + 1;
		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) { 
	for(int i = 1; i <= 17; i++) 
		if(par[u][i-1]) 
			par[u][i] = par[par[u][i-1]][i-1]; 

	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);  
		par[i][0] = p;
	} 
	MinDfs(root); 
	postDfs(root); 
	priority_queue<node> Q; 
	for(int i = 0; i < n; i++) {
		Q.push({post[i], i});
		prior[post[i]] = i;
		has[post[i]] = 0;
	}
	while(q--) {
		int c, x; 
		scanf("%d %d", &c, &x); 
		if(c == 1) {
			node u; 
			while(x--) {
				u = Q.top();
				has[u.u] = 1;
				Q.pop();  
			} printf("%d\n", u.u);
		} else {
			int y = x; 
			for(int i = 17; i >= 0; i--) if(par[y][i]) {
				if(has[par[y][i]]) y = par[y][i];
			}
			has[y] = 0;
			cout<<dep[x] - dep[y]<<endl;
			Q.push({y, prior[y]}); 
		}
	}
}

Compilation message

ballmachine.cpp: In function 'int main(int, const char**)':
ballmachine.cpp:40: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:42: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:57: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:48:15: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  postDfs(root); 
               ^

Subtask #1
19.2307692308 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 12276 KB Output is correct
2 Correct 243 ms 14412 KB Output is correct
3 Correct 186 ms 14412 KB Output is correct
4 Correct 0 ms 12276 KB Output is correct
5 Correct 3 ms 12276 KB Output is correct
6 Correct 0 ms 12276 KB Output is correct
7 Correct 3 ms 12276 KB Output is correct
8 Correct 0 ms 12276 KB Output is correct
9 Correct 6 ms 12408 KB Output is correct
10 Correct 43 ms 12804 KB Output is correct
11 Runtime error 226 ms 14412 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 283 ms 14412 KB Execution timed out (wall clock limit exceeded)
13 Runtime error 319 ms 14412 KB Execution timed out (wall clock limit exceeded)

Subtask #2
15.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 14180 KB Output is correct
2 Runtime error 319 ms 18580 KB Execution timed out (wall clock limit exceeded)
3 Correct 229 ms 15840 KB Output is correct
4 Runtime error 189 ms 14168 KB Execution timed out (wall clock limit exceeded)
5 Correct 246 ms 14036 KB Output is correct
6 Correct 169 ms 14036 KB Output is correct
7 Runtime error 206 ms 13616 KB Execution timed out (wall clock limit exceeded)
8 Correct 123 ms 14176 KB Output is correct
9 Runtime error 333 ms 19004 KB Execution timed out (wall clock limit exceeded)
10 Runtime error 286 ms 18580 KB Execution timed out (wall clock limit exceeded)
11 Runtime error 366 ms 18584 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 356 ms 17340 KB Execution timed out (wall clock limit exceeded)
13 Correct 276 ms 21184 KB Output is correct
14 Correct 123 ms 15840 KB Output is correct

Subtask #3
22.8571428571 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 169 ms 15620 KB Output is correct
2 Correct 386 ms 17412 KB Output is correct
3 Correct 279 ms 20532 KB Output is correct
4 Runtime error 243 ms 18064 KB Execution timed out (wall clock limit exceeded)
5 Correct 166 ms 17724 KB Output is correct
6 Correct 186 ms 17732 KB Output is correct
7 Correct 176 ms 16788 KB Output is correct
8 Runtime error 326 ms 20536 KB Execution timed out (wall clock limit exceeded)
9 Runtime error 353 ms 19008 KB Execution timed out (wall clock limit exceeded)
10 Runtime error 423 ms 18584 KB Execution timed out (wall clock limit exceeded)
11 Correct 486 ms 18596 KB Output is correct
12 Runtime error 439 ms 17408 KB Execution timed out (wall clock limit exceeded)
13 Correct 399 ms 22100 KB Output is correct
14 Runtime error 206 ms 15844 KB Execution timed out (wall clock limit exceeded)

Subtask #4
2.77777777778 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 246 ms 19000 KB Execution timed out (wall clock limit exceeded)
2 Runtime error 406 ms 17412 KB Execution timed out (wall clock limit exceeded)
3 Correct 269 ms 22100 KB Output is correct
4 Runtime error 326 ms 19000 KB Execution timed out (wall clock limit exceeded)
5 Correct 473 ms 18592 KB Output is correct
6 Runtime error 389 ms 18588 KB Execution timed out (wall clock limit exceeded)
7 Correct 369 ms 17408 KB Output is correct
8 Correct 249 ms 22100 KB Output is correct
9 Correct 179 ms 15844 KB Output is correct