Submission #302682

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
302682	2020-09-19T03:39:18 Z	eggag32	Ball Machine (BOI13_ballmachine)	C++17	97.1429 / 100	1000 ms	31732 KB

ballmachine

#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 l = 1, r = dep[x];
			while(l < r){
				int mid = (l + r) / 2;
				int nd = x;
				rep(j, le) if(mid & (1 << j)) nd = up[nd][j];
				if(!vis[nd]) r = mid;
				else l = mid + 1;
			}
			int cur = l;
			int nd = x;
			rep(j, le) if(cur & (1 << j)) nd = up[nd][j];
			if(!vis[nd]){
				cur--;
				nd = x;
				l--;
				rep(j, le) if(cur & (1 << j)) nd = up[nd][j];
			}
			vis[nd] = 0;
			st.insert({ind[nd], nd});
			cout << l << '\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	204 ms	16628 KB	Output is correct
3	Correct	109 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	4 ms	3328 KB	Output is correct
8	Correct	3 ms	3328 KB	Output is correct
9	Correct	10 ms	3840 KB	Output is correct
10	Correct	31 ms	6524 KB	Output is correct
11	Correct	204 ms	16628 KB	Output is correct
12	Correct	122 ms	16884 KB	Output is correct
13	Correct	162 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	293 ms	27508 KB	Output is correct
3	Correct	142 ms	23408 KB	Output is correct
4	Correct	90 ms	10616 KB	Output is correct
5	Correct	89 ms	10488 KB	Output is correct
6	Correct	83 ms	10488 KB	Output is correct
7	Correct	88 ms	9464 KB	Output is correct
8	Correct	43 ms	8448 KB	Output is correct
9	Correct	246 ms	27632 KB	Output is correct
10	Correct	297 ms	27624 KB	Output is correct
11	Correct	258 ms	27508 KB	Output is correct
12	Correct	280 ms	25076 KB	Output is correct
13	Correct	219 ms	28020 KB	Output is correct
14	Correct	136 ms	23408 KB	Output is correct

Subtask #3

37.1428571429 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	246 ms	15476 KB	Output is correct
2	Correct	730 ms	26032 KB	Output is correct
3	Correct	675 ms	26096 KB	Output is correct
4	Correct	458 ms	22824 KB	Output is correct
5	Correct	427 ms	22876 KB	Output is correct
6	Correct	425 ms	22896 KB	Output is correct
7	Correct	406 ms	21104 KB	Output is correct
8	Correct	685 ms	26112 KB	Output is correct
9	Correct	733 ms	27888 KB	Output is correct
10	Correct	774 ms	27892 KB	Output is correct
11	Correct	793 ms	27892 KB	Output is correct
12	Correct	758 ms	25844 KB	Output is correct
13	Execution timed out	1098 ms	31732 KB	Time limit exceeded
14	Correct	233 ms	23792 KB	Output is correct

Subtask #4

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	890 ms	28016 KB	Output is correct
2	Correct	659 ms	25972 KB	Output is correct
3	Correct	238 ms	31220 KB	Output is correct
4	Correct	845 ms	28016 KB	Output is correct
5	Correct	671 ms	27764 KB	Output is correct
6	Correct	410 ms	27832 KB	Output is correct
7	Correct	663 ms	25844 KB	Output is correct
8	Correct	238 ms	31220 KB	Output is correct
9	Correct	137 ms	23408 KB	Output is correct