oj.uz

답안 #30860

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

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 12828 KB Output isn't correct
2 Runtime error 33 ms 13884 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 66 ms 13884 KB Execution killed because of forbidden syscall writev (20)
4 Incorrect 0 ms 12828 KB Output isn't correct
5 Incorrect 3 ms 12828 KB Output isn't correct
6 Correct 3 ms 12828 KB Output is correct
7 Incorrect 3 ms 12828 KB Output isn't correct
8 Correct 3 ms 12828 KB Output is correct
9 Runtime error 3 ms 12828 KB Execution killed because of forbidden syscall writev (20)
10 Runtime error 13 ms 13092 KB Execution killed because of forbidden syscall writev (20)
11 Runtime error 59 ms 13884 KB Execution killed because of forbidden syscall writev (20)
12 Runtime error 53 ms 13884 KB Execution killed because of forbidden syscall writev (20)
13 Runtime error 56 ms 13884 KB Execution killed because of forbidden syscall writev (20)

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 19 ms 14656 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 149 ms 18584 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 83 ms 14276 KB Execution killed because of forbidden syscall writev (20)
4 Runtime error 16 ms 14532 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 26 ms 14400 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 33 ms 14400 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 13 ms 13768 KB Execution killed because of forbidden syscall writev (20)
8 Runtime error 13 ms 14656 KB Execution killed because of forbidden syscall writev (20)
9 Runtime error 123 ms 18984 KB Execution killed because of forbidden syscall writev (20)
10 Runtime error 166 ms 18584 KB Execution killed because of forbidden syscall writev (20)
11 Runtime error 126 ms 18588 KB Execution killed because of forbidden syscall writev (20)
12 Runtime error 116 ms 16460 KB Execution killed because of forbidden syscall writev (20)
13 Runtime error 113 ms 22372 KB Execution killed because of forbidden syscall writev (20)
14 Runtime error 63 ms 14276 KB Execution killed because of forbidden syscall writev (20)

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 43 ms 15844 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 173 ms 16636 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 79 ms 21460 KB Execution killed because of forbidden syscall writev (20)
4 Runtime error 106 ms 17676 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 126 ms 17412 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 96 ms 17412 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 86 ms 15852 KB Execution killed because of forbidden syscall writev (20)
8 Runtime error 123 ms 21460 KB Execution killed because of forbidden syscall writev (20)
9 Runtime error 123 ms 18988 KB Execution killed because of forbidden syscall writev (20)
10 Runtime error 133 ms 18592 KB Execution killed because of forbidden syscall writev (20)
11 Runtime error 119 ms 18592 KB Execution killed because of forbidden syscall writev (20)
12 Runtime error 93 ms 16636 KB Execution killed because of forbidden syscall writev (20)
13 Runtime error 149 ms 23552 KB Execution killed because of forbidden syscall writev (20)
14 Runtime error 103 ms 14276 KB Execution killed because of forbidden syscall writev (20)

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 123 ms 18984 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 133 ms 16640 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 156 ms 23552 KB Execution killed because of forbidden syscall writev (20)
4 Runtime error 123 ms 18984 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 146 ms 18592 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 116 ms 18588 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 126 ms 16632 KB Execution killed because of forbidden syscall writev (20)
8 Runtime error 136 ms 23552 KB Execution killed because of forbidden syscall writev (20)
9 Runtime error 69 ms 14276 KB Execution killed because of forbidden syscall writev (20)