oj.uz

Submission #302684

# Submission time Handle Problem Language Result Execution time Memory
302684 2020-09-19T03:52:18 Z eggag32 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 404 ms 31944 KB 
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl
#define debug2(x, y) debug(x), debug(y)
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))
#define inf 0x3f3f3f3f
const int mxN = 1e5 + 5;
 
template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }
 
int n, le;
int ind[mxN], mn[mxN], vis[mxN];
int st[mxN], fin[mxN], dep[mxN];
int num = 0, rt = -1;
vi g[mxN];
vector<vi> up;
 
void dfs0(int cur, int prev, int d = 0){
	mn[cur] = cur;
	dep[cur] = d;
	for(int x : g[cur]) if(x != prev){
		dfs0(x, cur, d + 1);
		mn[cur] = min(mn[cur], mn[x]);
	}
}
 
bool cmp(int a, int b){
	return mn[a] < mn[b];
}
 
vi ord;
 
void dfs(int cur, int prev = rt){
	st[cur] = num++;
	up[cur][0] = prev;
	repn(i, 1, le + 1) up[cur][i] = up[up[cur][i - 1]][i - 1];
	for(int x : g[cur]) if(x != prev) dfs(x, cur);
	ord.pb(cur);
	fin[cur] = num++;
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	int n, q;
	cin >> n >> q;
	memset(mn, inf, sizeof(mn));
	rep(i, n){
		int a;
		cin >> a;
		a--;
		if(a >= 0){
			g[i].pb(a);
			g[a].pb(i);
		}
		else rt = i;
	}
	dfs0(rt, -1); //get the minimums
	rep(i, n) sort(all(g[i]), cmp);
	up.resize(n);
	le = 1;
	while((1 << le) <= n) le++;
	rep(i, n) up[i].resize(le + 1);
	dfs(rt);
	rep(i, n) ind[ord[i]] = i;
	set<pi> st;
	rep(i, n) st.insert({ind[i], i}); //we sort by the index from the toposort
	rep(i, q){
		int t;
		cin >> t;
		if(t == 1){
			int k;
			cin >> k;
			int lst = -1;
			rep(j, k){
				pi cur = *st.begin();
				st.erase(st.begin());
				vis[cur.se] = 1;
				lst = cur.se;
			}
			cout << lst + 1 << '\n';
		}
		else{
			//we use binary search + binary lifting
			//to find the first unvisited node above the deleted one
			int x;
			cin >> x;
			x--;
			if(x == rt || !vis[up[x][0]]){
				cout << 0 << '\n';
				vis[x] = 0;
				st.insert({ind[x], x});
				continue;
			}
			int nd = x;
			for(int j = le; j >= 0; j--){
				int nd1 = up[nd][j];
				if(vis[nd1]) nd = nd1;
			}
			vis[nd] = 0;
			st.insert({ind[nd], nd});
			cout << dep[x] - dep[nd] << '\n';
		}
	}
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3200 KB Output is correct
2 Correct 195 ms 16628 KB Output is correct
3 Correct 108 ms 16628 KB Output is correct
4 Correct 2 ms 3072 KB Output is correct
5 Correct 3 ms 3200 KB Output is correct
6 Correct 3 ms 3328 KB Output is correct
7 Correct 3 ms 3328 KB Output is correct
8 Correct 4 ms 3328 KB Output is correct
9 Correct 10 ms 3840 KB Output is correct
10 Correct 31 ms 6528 KB Output is correct
11 Correct 193 ms 16628 KB Output is correct
12 Correct 116 ms 16628 KB Output is correct
13 Correct 160 ms 16628 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 8448 KB Output is correct
2 Correct 316 ms 27636 KB Output is correct
3 Correct 143 ms 23408 KB Output is correct
4 Correct 91 ms 10616 KB Output is correct
5 Correct 92 ms 10488 KB Output is correct
6 Correct 84 ms 10488 KB Output is correct
7 Correct 84 ms 9464 KB Output is correct
8 Correct 43 ms 8444 KB Output is correct
9 Correct 253 ms 27632 KB Output is correct
10 Correct 295 ms 27508 KB Output is correct
11 Correct 267 ms 27504 KB Output is correct
12 Correct 287 ms 25204 KB Output is correct
13 Correct 209 ms 28148 KB Output is correct
14 Correct 138 ms 23408 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 15476 KB Output is correct
2 Correct 353 ms 25716 KB Output is correct
3 Correct 265 ms 26096 KB Output is correct
4 Correct 223 ms 22768 KB Output is correct
5 Correct 234 ms 22768 KB Output is correct
6 Correct 254 ms 22896 KB Output is correct
7 Correct 235 ms 21232 KB Output is correct
8 Correct 261 ms 25968 KB Output is correct
9 Correct 345 ms 27756 KB Output is correct
10 Correct 367 ms 27764 KB Output is correct
11 Correct 384 ms 27892 KB Output is correct
12 Correct 374 ms 25848 KB Output is correct
13 Correct 404 ms 31944 KB Output is correct
14 Correct 255 ms 23792 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 28016 KB Output is correct
2 Correct 360 ms 25844 KB Output is correct
3 Correct 241 ms 31348 KB Output is correct
4 Correct 355 ms 28016 KB Output is correct
5 Correct 378 ms 27884 KB Output is correct
6 Correct 284 ms 27764 KB Output is correct
7 Correct 365 ms 25844 KB Output is correct
8 Correct 258 ms 31348 KB Output is correct
9 Correct 146 ms 23408 KB Output is correct