oj.uz

Submission #30857

# Submission time Handle Problem Language Result Execution time Memory
30857 2017-07-28T14:29:04 Z Navick Ball Machine (BOI13_ballmachine) C++14
0 / 100
 133 ms 24336 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);

	for(int i=0; i<n; i++)
		cout << g[i] << ' '; cout << endl;

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

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 13608 KB Output isn't correct
2 Runtime error 53 ms 14664 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 29 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 Incorrect 0 ms 13608 KB Output isn't correct
7 Incorrect 0 ms 13608 KB Output isn't correct
8 Incorrect 0 ms 13608 KB Output isn't correct
9 Runtime error 3 ms 13608 KB Execution killed because of forbidden syscall writev (20)
10 Runtime error 6 ms 13872 KB Execution killed because of forbidden syscall writev (20)
11 Runtime error 29 ms 14664 KB Execution killed because of forbidden syscall writev (20)
12 Runtime error 33 ms 14664 KB Execution killed because of forbidden syscall writev (20)
13 Runtime error 36 ms 14664 KB Execution killed because of forbidden syscall writev (20)

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 15436 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 69 ms 19360 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 46 ms 15056 KB Execution killed because of forbidden syscall writev (20)
4 Runtime error 9 ms 15312 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 16 ms 15176 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 16 ms 15176 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 13 ms 14548 KB Execution killed because of forbidden syscall writev (20)
8 Runtime error 6 ms 15436 KB Execution killed because of forbidden syscall writev (20)
9 Runtime error 86 ms 19768 KB Execution killed because of forbidden syscall writev (20)
10 Runtime error 96 ms 19364 KB Execution killed because of forbidden syscall writev (20)
11 Runtime error 133 ms 19364 KB Execution killed because of forbidden syscall writev (20)
12 Runtime error 73 ms 17240 KB Execution killed because of forbidden syscall writev (20)
13 Runtime error 113 ms 23148 KB Execution killed because of forbidden syscall writev (20)
14 Runtime error 46 ms 15056 KB Execution killed because of forbidden syscall writev (20)

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 16620 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 133 ms 17416 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 69 ms 22236 KB Execution killed because of forbidden syscall writev (20)
4 Runtime error 49 ms 18452 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 49 ms 18188 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 96 ms 18192 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 49 ms 16632 KB Execution killed because of forbidden syscall writev (20)
8 Runtime error 56 ms 22236 KB Execution killed because of forbidden syscall writev (20)
9 Runtime error 53 ms 19768 KB Execution killed because of forbidden syscall writev (20)
10 Runtime error 66 ms 19368 KB Execution killed because of forbidden syscall writev (20)
11 Runtime error 76 ms 19368 KB Execution killed because of forbidden syscall writev (20)
12 Runtime error 69 ms 17416 KB Execution killed because of forbidden syscall writev (20)
13 Runtime error 96 ms 24328 KB Execution killed because of forbidden syscall writev (20)
14 Runtime error 66 ms 15056 KB Execution killed because of forbidden syscall writev (20)

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 69 ms 19768 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 123 ms 17416 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 89 ms 24336 KB Execution killed because of forbidden syscall writev (20)
4 Runtime error 126 ms 19764 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 89 ms 19364 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 93 ms 19368 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 126 ms 17416 KB Execution killed because of forbidden syscall writev (20)
8 Runtime error 129 ms 24328 KB Execution killed because of forbidden syscall writev (20)
9 Runtime error 76 ms 15056 KB Execution killed because of forbidden syscall writev (20)