Submission #302677

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
302677	2020-09-19T03:27:44 Z	eggag32	Ball Machine (BOI13_ballmachine)	C++17	97.1429 / 100	1000 ms	31856 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 dfs1(int cur, int prev){
	for(int x : g[cur]) if(x != prev) dfs1(x, cur);
	ord.pb(cur);
}

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);
	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);
	dfs1(rt, -1);
	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
	up.resize(n);
	le = 1;
	while((1 << le) <= n) le++;
	rep(i, n) up[i].resize(le + 1);
	dfs(rt);
	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 + 1) 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 + 1) if(cur & (1 << j)) nd = up[nd][j];
			if(!vis[nd]){
				cur--;
				nd = x;
				l--;
				rep(j, le + 1) 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	199 ms	16628 KB	Output is correct
3	Correct	105 ms	16628 KB	Output is correct
4	Correct	2 ms	3072 KB	Output is correct
5	Correct	3 ms	3328 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	31 ms	6520 KB	Output is correct
11	Correct	206 ms	16628 KB	Output is correct
12	Correct	104 ms	16628 KB	Output is correct
13	Correct	168 ms	16756 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	289 ms	27508 KB	Output is correct
3	Correct	136 ms	23408 KB	Output is correct
4	Correct	84 ms	10620 KB	Output is correct
5	Correct	86 ms	10488 KB	Output is correct
6	Correct	75 ms	10488 KB	Output is correct
7	Correct	81 ms	9592 KB	Output is correct
8	Correct	44 ms	8448 KB	Output is correct
9	Correct	246 ms	27752 KB	Output is correct
10	Correct	292 ms	27504 KB	Output is correct
11	Correct	242 ms	27508 KB	Output is correct
12	Correct	262 ms	25072 KB	Output is correct
13	Correct	198 ms	28012 KB	Output is correct
14	Correct	129 ms	23408 KB	Output is correct

Subtask #3

37.1428571429 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	234 ms	15480 KB	Output is correct
2	Correct	689 ms	25748 KB	Output is correct
3	Correct	659 ms	26104 KB	Output is correct
4	Correct	474 ms	22872 KB	Output is correct
5	Correct	414 ms	22768 KB	Output is correct
6	Correct	416 ms	22900 KB	Output is correct
7	Correct	388 ms	21236 KB	Output is correct
8	Correct	670 ms	26096 KB	Output is correct
9	Correct	733 ms	27888 KB	Output is correct
10	Correct	823 ms	27804 KB	Output is correct
11	Correct	778 ms	27888 KB	Output is correct
12	Correct	709 ms	25844 KB	Output is correct
13	Execution timed out	1095 ms	31856 KB	Time limit exceeded
14	Correct	232 ms	23924 KB	Output is correct

Subtask #4

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	877 ms	28020 KB	Output is correct
2	Correct	647 ms	25844 KB	Output is correct
3	Correct	237 ms	31344 KB	Output is correct
4	Correct	861 ms	28016 KB	Output is correct
5	Correct	697 ms	27892 KB	Output is correct
6	Correct	409 ms	27764 KB	Output is correct
7	Correct	652 ms	25844 KB	Output is correct
8	Correct	240 ms	31268 KB	Output is correct
9	Correct	133 ms	23408 KB	Output is correct