oj.uz

답안 #30861

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
30861 2017-07-28T14:50:16 Z Navick Ball Machine (BOI13_ballmachine) C++14
11.5385 / 100
 206 ms 28308 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 63 ms 16924 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 69 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 16 ms 13888 KB Execution killed because of forbidden syscall writev (20)
11 Runtime error 79 ms 16924 KB Execution killed because of forbidden syscall writev (20)
12 Runtime error 66 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 23 ms 15580 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 116 ms 23204 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 113 ms 18900 KB Execution killed because of forbidden syscall writev (20)
4 Runtime error 26 ms 15992 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 29 ms 15856 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 23 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 193 ms 23608 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 139 ms 23212 KB Execution killed because of forbidden syscall writev (20)
12 Runtime error 203 ms 21080 KB Execution killed because of forbidden syscall writev (20)
13 Runtime error 186 ms 26464 KB Execution killed because of forbidden syscall writev (20)
14 Runtime error 133 ms 18900 KB Execution killed because of forbidden syscall writev (20)

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 39 ms 18092 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 189 ms 21260 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 129 ms 25160 KB Execution killed because of forbidden syscall writev (20)
4 Runtime error 129 ms 21508 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 146 ms 21112 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 86 ms 21108 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 86 ms 19548 KB Execution killed because of forbidden syscall writev (20)
8 Runtime error 76 ms 25160 KB Execution killed because of forbidden syscall writev (20)
9 Runtime error 106 ms 23612 KB Execution killed because of forbidden syscall writev (20)
10 Runtime error 116 ms 23216 KB Execution killed because of forbidden syscall writev (20)
11 Runtime error 199 ms 23212 KB Execution killed because of forbidden syscall writev (20)
12 Runtime error 183 ms 21260 KB Execution killed because of forbidden syscall writev (20)
13 Runtime error 196 ms 28304 KB Execution killed because of forbidden syscall writev (20)
14 Runtime error 103 ms 18900 KB Execution killed because of forbidden syscall writev (20)

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 163 ms 23612 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 176 ms 21256 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 196 ms 28304 KB Execution killed because of forbidden syscall writev (20)
4 Runtime error 159 ms 23608 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 206 ms 23208 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 206 ms 23216 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 206 ms 21264 KB Execution killed because of forbidden syscall writev (20)
8 Runtime error 169 ms 28308 KB Execution killed because of forbidden syscall writev (20)
9 Runtime error 76 ms 18900 KB Execution killed because of forbidden syscall writev (20)