oj.uz

답안 #30896

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
30896 2017-07-31T12:55:41 Z Navick Ball Machine (BOI13_ballmachine) C++14
11.5385 / 100
 216 ms 28312 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
11.5384615385 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 12832 KB Output is correct
2 Runtime error 53 ms 16924 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 46 ms 16924 KB Execution killed because of forbidden syscall writev (20)
4 Correct 0 ms 12832 KB Output is correct
5 Correct 0 ms 12832 KB Output is correct
6 Correct 0 ms 12832 KB Output is correct
7 Correct 0 ms 12832 KB Output is correct
8 Correct 0 ms 12832 KB Output is correct
9 Runtime error 3 ms 13096 KB Execution killed because of forbidden syscall writev (20)
10 Runtime error 6 ms 13888 KB Execution killed because of forbidden syscall writev (20)
11 Runtime error 73 ms 16924 KB Execution killed because of forbidden syscall writev (20)
12 Runtime error 76 ms 16924 KB Execution killed because of forbidden syscall writev (20)
13 Runtime error 86 ms 16924 KB Execution killed because of forbidden syscall writev (20)

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 16 ms 15588 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 196 ms 23204 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 109 ms 18900 KB Execution killed because of forbidden syscall writev (20)
4 Runtime error 39 ms 15988 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 33 ms 15852 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 43 ms 15852 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 29 ms 15096 KB Execution killed because of forbidden syscall writev (20)
8 Runtime error 13 ms 15588 KB Execution killed because of forbidden syscall writev (20)
9 Runtime error 153 ms 23608 KB Execution killed because of forbidden syscall writev (20)
10 Runtime error 183 ms 23208 KB Execution killed because of forbidden syscall writev (20)
11 Runtime error 179 ms 23208 KB Execution killed because of forbidden syscall writev (20)
12 Runtime error 163 ms 21084 KB Execution killed because of forbidden syscall writev (20)
13 Runtime error 166 ms 26468 KB Execution killed because of forbidden syscall writev (20)
14 Runtime error 113 ms 18900 KB Execution killed because of forbidden syscall writev (20)

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 73 ms 18096 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 216 ms 21264 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 139 ms 25164 KB Execution killed because of forbidden syscall writev (20)
4 Runtime error 119 ms 21508 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 123 ms 21116 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 139 ms 21116 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 149 ms 19552 KB Execution killed because of forbidden syscall writev (20)
8 Runtime error 153 ms 25160 KB Execution killed because of forbidden syscall writev (20)
9 Runtime error 163 ms 23612 KB Execution killed because of forbidden syscall writev (20)
10 Runtime error 183 ms 23212 KB Execution killed because of forbidden syscall writev (20)
11 Runtime error 206 ms 23212 KB Execution killed because of forbidden syscall writev (20)
12 Runtime error 173 ms 21260 KB Execution killed because of forbidden syscall writev (20)
13 Runtime error 193 ms 28312 KB Execution killed because of forbidden syscall writev (20)
14 Runtime error 116 ms 18900 KB Execution killed because of forbidden syscall writev (20)

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 149 ms 23608 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 176 ms 21260 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 179 ms 28308 KB Execution killed because of forbidden syscall writev (20)
4 Runtime error 166 ms 23608 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 179 ms 23208 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 183 ms 23212 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 166 ms 21260 KB Execution killed because of forbidden syscall writev (20)
8 Runtime error 176 ms 28304 KB Execution killed because of forbidden syscall writev (20)
9 Runtime error 96 ms 18900 KB Execution killed because of forbidden syscall writev (20)