oj.uz

답안 #30858

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
30858 2017-07-28T14:29:55 Z Navick Ball Machine (BOI13_ballmachine) C++14
3.84615 / 100
 173 ms 24332 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 = 20;

bool full[N];
vector<int> adj[N];
int n, root, g[N], mn[N], par[N][LOG], ord[N], turn = 0;

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 lo = -1, hi = n;
	while(hi - lo > 1){
		int mid = (lo + hi)/2;
		if(!full[g[mid]])hi = mid;
		else lo = mid;
	}
	full[g[hi]] = true;
	return g[hi];
}

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;
	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);

	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
3.84615384615 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 13608 KB Output isn't correct
2 Runtime error 59 ms 14664 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 59 ms 14664 KB Execution killed because of forbidden syscall writev (20)
4 Incorrect 0 ms 13608 KB Output isn't correct
5 Incorrect 0 ms 13608 KB Output isn't correct
6 Correct 3 ms 13608 KB Output is correct
7 Incorrect 0 ms 13608 KB Output isn't correct
8 Correct 3 ms 13608 KB Output is correct
9 Runtime error 3 ms 13608 KB Execution killed because of forbidden syscall writev (20)
10 Runtime error 9 ms 13872 KB Execution killed because of forbidden syscall writev (20)
11 Runtime error 56 ms 14664 KB Execution killed because of forbidden syscall writev (20)
12 Runtime error 49 ms 14664 KB Execution killed because of forbidden syscall writev (20)
13 Runtime error 63 ms 14664 KB Execution killed because of forbidden syscall writev (20)

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 19 ms 15436 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 143 ms 19360 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 56 ms 15056 KB Execution killed because of forbidden syscall writev (20)
4 Runtime error 19 ms 15316 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 43 ms 15180 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 19 ms 15180 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 13 ms 14552 KB Execution killed because of forbidden syscall writev (20)
8 Runtime error 6 ms 15440 KB Execution killed because of forbidden syscall writev (20)
9 Runtime error 73 ms 19764 KB Execution killed because of forbidden syscall writev (20)
10 Runtime error 79 ms 19364 KB Execution killed because of forbidden syscall writev (20)
11 Runtime error 83 ms 19368 KB Execution killed because of forbidden syscall writev (20)
12 Runtime error 119 ms 17236 KB Execution killed because of forbidden syscall writev (20)
13 Runtime error 133 ms 23148 KB Execution killed because of forbidden syscall writev (20)
14 Runtime error 73 ms 15056 KB Execution killed because of forbidden syscall writev (20)

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 33 ms 16624 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 116 ms 17416 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 59 ms 22244 KB Execution killed because of forbidden syscall writev (20)
4 Runtime error 56 ms 18460 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 109 ms 18196 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 66 ms 18192 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 69 ms 16628 KB Execution killed because of forbidden syscall writev (20)
8 Runtime error 63 ms 22240 KB Execution killed because of forbidden syscall writev (20)
9 Runtime error 116 ms 19764 KB Execution killed because of forbidden syscall writev (20)
10 Runtime error 86 ms 19368 KB Execution killed because of forbidden syscall writev (20)
11 Runtime error 136 ms 19368 KB Execution killed because of forbidden syscall writev (20)
12 Runtime error 116 ms 17420 KB Execution killed because of forbidden syscall writev (20)
13 Runtime error 96 ms 24332 KB Execution killed because of forbidden syscall writev (20)
14 Runtime error 63 ms 15056 KB Execution killed because of forbidden syscall writev (20)

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 83 ms 19764 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 156 ms 17416 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 173 ms 24332 KB Execution killed because of forbidden syscall writev (20)
4 Runtime error 86 ms 19768 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 106 ms 19368 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 123 ms 19368 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 99 ms 17416 KB Execution killed because of forbidden syscall writev (20)
8 Runtime error 103 ms 24332 KB Execution killed because of forbidden syscall writev (20)
9 Runtime error 83 ms 15056 KB Execution killed because of forbidden syscall writev (20)