oj.uz

Submission #302687

# Submission time Handle Problem Language Result Execution time Memory
302687 2020-09-19T04:03:52 Z eggag32 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 450 ms 31864 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 206 ms 16628 KB Output is correct
3 Correct 111 ms 16628 KB Output is correct
4 Correct 2 ms 3072 KB Output is correct
5 Correct 2 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 33 ms 6528 KB Output is correct
11 Correct 217 ms 16720 KB Output is correct
12 Correct 111 ms 16628 KB Output is correct
13 Correct 163 ms 16628 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 8448 KB Output is correct
2 Correct 298 ms 27636 KB Output is correct
3 Correct 142 ms 23408 KB Output is correct
4 Correct 97 ms 10640 KB Output is correct
5 Correct 89 ms 10492 KB Output is correct
6 Correct 94 ms 10488 KB Output is correct
7 Correct 97 ms 9464 KB Output is correct
8 Correct 42 ms 8440 KB Output is correct
9 Correct 251 ms 27580 KB Output is correct
10 Correct 313 ms 27508 KB Output is correct
11 Correct 258 ms 27636 KB Output is correct
12 Correct 271 ms 25048 KB Output is correct
13 Correct 211 ms 28020 KB Output is correct
14 Correct 146 ms 23408 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 15476 KB Output is correct
2 Correct 363 ms 25844 KB Output is correct
3 Correct 247 ms 25968 KB Output is correct
4 Correct 219 ms 22768 KB Output is correct
5 Correct 237 ms 22804 KB Output is correct
6 Correct 233 ms 22712 KB Output is correct
7 Correct 231 ms 21104 KB Output is correct
8 Correct 243 ms 25968 KB Output is correct
9 Correct 337 ms 27760 KB Output is correct
10 Correct 379 ms 27896 KB Output is correct
11 Correct 365 ms 27764 KB Output is correct
12 Correct 354 ms 25844 KB Output is correct
13 Correct 450 ms 31864 KB Output is correct
14 Correct 243 ms 23792 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 27888 KB Output is correct
2 Correct 343 ms 25720 KB Output is correct
3 Correct 241 ms 31352 KB Output is correct
4 Correct 333 ms 27888 KB Output is correct
5 Correct 358 ms 27708 KB Output is correct
6 Correct 293 ms 27636 KB Output is correct
7 Correct 346 ms 25880 KB Output is correct
8 Correct 236 ms 31348 KB Output is correct
9 Correct 136 ms 23448 KB Output is correct