Submission #302686

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
302686	2020-09-19T04:01:08 Z	eggag32	Ball Machine (BOI13_ballmachine)	C++17	97.1429 / 100	1000 ms	31988 KB

ballmachine

#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	2 ms	3200 KB	Output is correct
2	Correct	199 ms	16660 KB	Output is correct
3	Correct	120 ms	16640 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	3 ms	3328 KB	Output is correct
9	Correct	10 ms	3840 KB	Output is correct
10	Correct	35 ms	6528 KB	Output is correct
11	Correct	206 ms	16628 KB	Output is correct
12	Correct	114 ms	16628 KB	Output is correct
13	Correct	170 ms	16628 KB	Output is correct

Subtask #2

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	43 ms	8440 KB	Output is correct
2	Correct	302 ms	27584 KB	Output is correct
3	Correct	146 ms	23404 KB	Output is correct
4	Correct	90 ms	10616 KB	Output is correct
5	Correct	91 ms	10576 KB	Output is correct
6	Correct	78 ms	10488 KB	Output is correct
7	Correct	88 ms	9464 KB	Output is correct
8	Correct	49 ms	8440 KB	Output is correct
9	Correct	261 ms	27640 KB	Output is correct
10	Correct	307 ms	27636 KB	Output is correct
11	Correct	262 ms	27512 KB	Output is correct
12	Correct	296 ms	25076 KB	Output is correct
13	Correct	217 ms	28020 KB	Output is correct
14	Correct	140 ms	23376 KB	Output is correct

Subtask #3

37.1428571429 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	241 ms	15500 KB	Output is correct
2	Correct	738 ms	25844 KB	Output is correct
3	Correct	687 ms	26096 KB	Output is correct
4	Correct	481 ms	22896 KB	Output is correct
5	Correct	432 ms	22812 KB	Output is correct
6	Correct	492 ms	22768 KB	Output is correct
7	Correct	415 ms	21232 KB	Output is correct
8	Correct	673 ms	26096 KB	Output is correct
9	Correct	743 ms	27760 KB	Output is correct
10	Correct	806 ms	27892 KB	Output is correct
11	Correct	822 ms	27904 KB	Output is correct
12	Correct	749 ms	25860 KB	Output is correct
13	Execution timed out	1095 ms	31988 KB	Time limit exceeded
14	Correct	237 ms	23828 KB	Output is correct

Subtask #4

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	901 ms	28132 KB	Output is correct
2	Correct	674 ms	25844 KB	Output is correct
3	Correct	262 ms	31220 KB	Output is correct
4	Correct	905 ms	28016 KB	Output is correct
5	Correct	744 ms	27888 KB	Output is correct
6	Correct	437 ms	27760 KB	Output is correct
7	Correct	685 ms	25716 KB	Output is correct
8	Correct	241 ms	31348 KB	Output is correct
9	Correct	142 ms	23408 KB	Output is correct