Submission #302678

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
302678	2020-09-19T03:34:09 Z	eggag32	Ball Machine (BOI13_ballmachine)	C++17	97.1429 / 100	1000 ms	27752 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];
}

bool cmp1(pi a, pi b){
	return a.fi > b.fi;
}

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;
	priority_queue<pi, vector<pi>, function<bool(pi, pi)>> st(cmp1);
	rep(i, n) st.push({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.top();
				st.pop();
				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.push({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.push({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	152 ms	14064 KB	Output is correct
3	Correct	97 ms	14064 KB	Output is correct
4	Correct	3 ms	3072 KB	Output is correct
5	Correct	3 ms	3072 KB	Output is correct
6	Correct	4 ms	3200 KB	Output is correct
7	Correct	3 ms	3200 KB	Output is correct
8	Correct	4 ms	3200 KB	Output is correct
9	Correct	9 ms	3712 KB	Output is correct
10	Correct	29 ms	5888 KB	Output is correct
11	Correct	156 ms	14064 KB	Output is correct
12	Correct	98 ms	14064 KB	Output is correct
13	Correct	142 ms	14064 KB	Output is correct

Subtask #2

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	7796 KB	Output is correct
2	Correct	275 ms	23660 KB	Output is correct
3	Correct	122 ms	19564 KB	Output is correct
4	Correct	79 ms	9332 KB	Output is correct
5	Correct	86 ms	9460 KB	Output is correct
6	Correct	76 ms	9332 KB	Output is correct
7	Correct	82 ms	8416 KB	Output is correct
8	Correct	46 ms	7796 KB	Output is correct
9	Correct	220 ms	23664 KB	Output is correct
10	Correct	261 ms	23700 KB	Output is correct
11	Correct	237 ms	23664 KB	Output is correct
12	Correct	233 ms	21484 KB	Output is correct
13	Correct	194 ms	24684 KB	Output is correct
14	Correct	120 ms	19436 KB	Output is correct

Subtask #3

37.1428571429 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	191 ms	13424 KB	Output is correct
2	Correct	630 ms	21916 KB	Output is correct
3	Correct	644 ms	22896 KB	Output is correct
4	Correct	406 ms	19692 KB	Output is correct
5	Correct	369 ms	19604 KB	Output is correct
6	Correct	412 ms	19732 KB	Output is correct
7	Correct	341 ms	18076 KB	Output is correct
8	Correct	673 ms	22896 KB	Output is correct
9	Correct	631 ms	23920 KB	Output is correct
10	Correct	707 ms	23920 KB	Output is correct
11	Correct	753 ms	23900 KB	Output is correct
12	Correct	684 ms	21872 KB	Output is correct
13	Execution timed out	1099 ms	27752 KB	Time limit exceeded
14	Correct	167 ms	19948 KB	Output is correct

Subtask #4

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	896 ms	23920 KB	Output is correct
2	Correct	628 ms	21876 KB	Output is correct
3	Correct	216 ms	27368 KB	Output is correct
4	Correct	832 ms	24048 KB	Output is correct
5	Correct	611 ms	23924 KB	Output is correct
6	Correct	373 ms	23788 KB	Output is correct
7	Correct	624 ms	22128 KB	Output is correct
8	Correct	217 ms	27372 KB	Output is correct
9	Correct	123 ms	19692 KB	Output is correct