oj.uz

답안 #30862

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
30862 2017-07-28T18:15:37 Z Navick Ball Machine (BOI13_ballmachine) C++14
45.2259 / 100
 543 ms 28152 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; cin >> n >> q;
	for(int i=1; i<=n; i++){
		int p; cin >> 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; cin >> k;
			while(k--)
				pos = add();
			cout << pos << '\n';
		}else{
			int v; cin >> v;
			cout << erase(v) << '\n';
		}
	}
}

Subtask #1
15.3846153846 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 12672 KB Output is correct
2 Runtime error 393 ms 16764 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 236 ms 16764 KB Execution timed out (wall clock limit exceeded)
4 Correct 0 ms 12672 KB Output is correct
5 Correct 0 ms 12672 KB Output is correct
6 Correct 0 ms 12804 KB Output is correct
7 Correct 6 ms 12804 KB Output is correct
8 Correct 6 ms 12804 KB Output is correct
9 Correct 39 ms 12936 KB Output is correct
10 Correct 109 ms 13728 KB Output is correct
11 Runtime error 399 ms 16764 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 183 ms 16764 KB Execution timed out (wall clock limit exceeded)
13 Runtime error 329 ms 16764 KB Execution timed out (wall clock limit exceeded)

Subtask #2
15.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 189 ms 15424 KB Output is correct
2 Runtime error 456 ms 23048 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 203 ms 18768 KB Execution timed out (wall clock limit exceeded)
4 Correct 293 ms 15836 KB Output is correct
5 Correct 296 ms 15692 KB Output is correct
6 Runtime error 176 ms 15696 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 253 ms 14932 KB Execution timed out (wall clock limit exceeded)
8 Correct 186 ms 15424 KB Output is correct
9 Runtime error 366 ms 23580 KB Execution timed out (wall clock limit exceeded)
10 Runtime error 399 ms 23048 KB Execution timed out (wall clock limit exceeded)
11 Runtime error 419 ms 23048 KB Execution timed out (wall clock limit exceeded)
12 Correct 516 ms 20924 KB Output is correct
13 Correct 449 ms 26304 KB Output is correct
14 Correct 316 ms 18768 KB Output is correct

Subtask #3
14.2857142857 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 269 ms 18064 KB Output is correct
2 Runtime error 443 ms 21100 KB Execution timed out (wall clock limit exceeded)
3 Runtime error 413 ms 25000 KB Execution timed out (wall clock limit exceeded)
4 Runtime error 406 ms 21352 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 423 ms 20952 KB Execution timed out (wall clock limit exceeded)
6 Correct 433 ms 20948 KB Output is correct
7 Correct 453 ms 19384 KB Output is correct
8 Correct 333 ms 25000 KB Output is correct
9 Runtime error 423 ms 23580 KB Execution timed out (wall clock limit exceeded)
10 Correct 486 ms 23052 KB Output is correct
11 Runtime error 346 ms 23052 KB Execution timed out (wall clock limit exceeded)
12 Runtime error 469 ms 21096 KB Execution timed out (wall clock limit exceeded)
13 Runtime error 406 ms 28152 KB Execution timed out (wall clock limit exceeded)
14 Runtime error 446 ms 18756 KB Execution timed out (wall clock limit exceeded)

Subtask #4
0.555555555556 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 463 ms 23580 KB Execution timed out (wall clock limit exceeded)
2 Runtime error 543 ms 21100 KB Execution timed out (wall clock limit exceeded)
3 Correct 456 ms 28144 KB Output is correct
4 Runtime error 453 ms 23580 KB Execution timed out (wall clock limit exceeded)
5 Runtime error 416 ms 23056 KB Execution timed out (wall clock limit exceeded)
6 Runtime error 383 ms 23052 KB Execution timed out (wall clock limit exceeded)
7 Runtime error 526 ms 21100 KB Execution timed out (wall clock limit exceeded)
8 Runtime error 349 ms 28148 KB Execution timed out (wall clock limit exceeded)
9 Runtime error 299 ms 18760 KB Execution timed out (wall clock limit exceeded)