oj.uz

답안 #30863

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
30863 2017-07-28T18:21:40 Z Navick Ball Machine (BOI13_ballmachine) C++14
39.4506 / 100
 579 ms 28148 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
const int N = 1e5 + 10, LOG = 18;
 
bool full[N];
vector<int> adj[N];
int n, root, g[N], mn[N], par[N][LOG], ord[N], turn = 0;
 
set<pii> st;
 
bool cmp(int u, int v){
	return mn[u] < mn[v];
}
 
bool pmc(int u, int v){
	return ord[u] < ord[v];
}
 
void p_dfs(int v, int p = 0){
	par[v][0] = p;
	for(int i=1; i<LOG; i++)
		par[v][i] = par[par[v][i - 1]][i - 1];
	
	mn[v] = v;
	for(auto u : adj[v]){
		p_dfs(u, v);
		mn[v] = min(mn[v], mn[u]);
	}
 
	sort(adj[v].begin(), adj[v].end(), cmp);
	
}
 
void dfs(int v){
	for(auto u : adj[v])
		dfs(u);
 
	ord[v] = turn++;
}
 
int add(){
	int v = (*st.begin()).S;
	st.erase(st.begin());
	full[v] = true;
	return v;
}
 
int erase(int v){
	int ans = 0;
	for(int i=LOG-1; i>=0; i--){
		if(full[par[v][i]]){
			ans += (1 << i);
			v = par[v][i];
		}
	}
	full[v] = false;
	st.insert({ord[v], v});
	return ans;
}
 
int main(){
	//ios_base::sync_with_stdio(0); cin.tie(0);
	int q; scanf("%d %d", &n, &q);
	for(int i=1; i<=n; i++){
		int p; scanf("%d", &p);
		if(p == 0)root = i;
		else adj[p].pb(i);
	}
 
	p_dfs(root);
	dfs(root);
 
	for(int i=0; i<n; i++)
		g[i] = i + 1;
 
	sort(g, g + n, pmc);
 
	for(int i=1; i<=n; i++)
		st.insert({ord[i], i});
 
	while(q--){
		int tp; cin >> tp;
		if(tp == 1){
			int k, pos = -1; scanf("%d", &k);
			while(k--)
				pos = add();
          printf("%d\n", pos);
		}else{
			int v; scanf("%d", &v);
			printf("%d\n", erase(v));
		}
	}
}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:72:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int q; scanf("%d %d", &n, &q);
                               ^
ballmachine.cpp:74: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:93:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int k, pos = -1; scanf("%d", &k);
                                    ^
ballmachine.cpp:98:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int v; scanf("%d", &v);
                          ^

Subtask #1
17.3076923077 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12672 KB Output is correct
2 Runtime error 366 ms 16764 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 223 ms 16764 KB Execution timed out (wall clock limit exceeded)
4 Correct 0 ms 12672 KB Output is correct
5 Correct 3 ms 12672 KB Output is correct
6 Correct 3 ms 12804 KB Output is correct
7 Correct 3 ms 12804 KB Output is correct
8 Correct 6 ms 12804 KB Output is correct
9 Correct 13 ms 12936 KB Output is correct
10 Correct 86 ms 13728 KB Output is correct
11 Runtime error 483 ms 16764 KB Execution timed out (wall clock limit exceeded)
12 Correct 269 ms 16764 KB Output is correct
13 Runtime error 283 ms 16764 KB Execution timed out (wall clock limit exceeded)

Subtask #2
10.7142857143 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 246 ms 15428 KB Output is correct
2 Runtime error 396 ms 23048 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 286 ms 18768 KB Execution timed out (wall clock limit exceeded)
4 Correct 363 ms 15832 KB Output is correct
5 Correct 289 ms 15692 KB Output is correct
6 Runtime error 243 ms 15692 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 233 ms 14932 KB Execution timed out (wall clock limit exceeded)
8 Runtime error 253 ms 15420 KB Execution timed out (wall clock limit exceeded)
9 Runtime error 353 ms 23576 KB Execution timed out (wall clock limit exceeded)
10 Runtime error 436 ms 23044 KB Execution timed out (wall clock limit exceeded)
11 Correct 403 ms 23048 KB Output is correct
12 Runtime error 373 ms 20920 KB Execution timed out (wall clock limit exceeded)
13 Runtime error 333 ms 26304 KB Execution timed out (wall clock limit exceeded)
14 Correct 319 ms 18768 KB Output is correct

Subtask #3
11.4285714286 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 323 ms 18064 KB Output is correct
2 Runtime error 529 ms 21100 KB Execution timed out (wall clock limit exceeded)
3 Correct 339 ms 25004 KB Output is correct
4 Runtime error 349 ms 21344 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 433 ms 20952 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 353 ms 20952 KB Execution timed out (wall clock limit exceeded)
7 Correct 443 ms 19392 KB Output is correct
8 Runtime error 449 ms 25000 KB Execution timed out (wall clock limit exceeded)
9 Runtime error 516 ms 23584 KB Execution timed out (wall clock limit exceeded)
10 Correct 486 ms 23052 KB Output is correct
11 Runtime error 476 ms 23056 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 523 ms 21100 KB Execution timed out (wall clock limit exceeded)
13 Runtime error 553 ms 28144 KB Execution timed out (wall clock limit exceeded)
14 Runtime error 389 ms 18756 KB Execution timed out (wall clock limit exceeded)

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 486 ms 23580 KB Execution timed out (wall clock limit exceeded)
2 Runtime error 326 ms 21104 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 343 ms 28148 KB Execution timed out (wall clock limit exceeded)
4 Runtime error 579 ms 23580 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 513 ms 23052 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 419 ms 23052 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 409 ms 21100 KB Execution timed out (wall clock limit exceeded)
8 Runtime error 349 ms 28144 KB Execution timed out (wall clock limit exceeded)
9 Runtime error 279 ms 18760 KB Execution timed out (wall clock limit exceeded)