oj.uz

Submission #302683

# Submission time Handle Problem Language Result Execution time Memory
302683 2020-09-19T03:46:37 Z eggag32 Ball Machine (BOI13_ballmachine) C++17
80.0794 / 100
 1000 ms 31608 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(){
	int q;
	scanf("%d%d", &n, &q);
	memset(mn, inf, sizeof(mn));
	rep(i, n){
		int a;
		scanf("%d", &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;
			}
			printf("%d\n", lst + 1);
		}
		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]]){
				printf("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});
			printf("%d\n", l);
		}
	}
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
ballmachine.cpp:63:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |   scanf("%d", &a);
      |   ~~~~~^~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3072 KB Output is correct
2 Correct 524 ms 16628 KB Output is correct
3 Correct 394 ms 16628 KB Output is correct
4 Correct 3 ms 3072 KB Output is correct
5 Correct 3 ms 3072 KB Output is correct
6 Correct 5 ms 3328 KB Output is correct
7 Correct 6 ms 3328 KB Output is correct
8 Correct 7 ms 3328 KB Output is correct
9 Correct 36 ms 3840 KB Output is correct
10 Correct 94 ms 6528 KB Output is correct
11 Correct 511 ms 16756 KB Output is correct
12 Correct 398 ms 16632 KB Output is correct
13 Correct 480 ms 16756 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 8440 KB Output is correct
2 Correct 608 ms 27632 KB Output is correct
3 Correct 409 ms 23660 KB Output is correct
4 Correct 328 ms 10488 KB Output is correct
5 Correct 337 ms 10488 KB Output is correct
6 Correct 317 ms 10488 KB Output is correct
7 Correct 325 ms 9464 KB Output is correct
8 Correct 264 ms 8440 KB Output is correct
9 Correct 562 ms 27636 KB Output is correct
10 Correct 594 ms 27632 KB Output is correct
11 Correct 551 ms 27544 KB Output is correct
12 Correct 585 ms 25116 KB Output is correct
13 Correct 480 ms 28016 KB Output is correct
14 Correct 401 ms 23664 KB Output is correct

Subtask #3
22.8571428571 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 15352 KB Output is correct
2 Execution timed out 1054 ms 25840 KB Time limit exceeded
3 Correct 864 ms 25972 KB Output is correct
4 Correct 695 ms 22752 KB Output is correct
5 Correct 643 ms 22832 KB Output is correct
6 Correct 625 ms 22816 KB Output is correct
7 Correct 613 ms 21236 KB Output is correct
8 Correct 890 ms 26056 KB Output is correct
9 Execution timed out 1091 ms 27992 KB Time limit exceeded
10 Execution timed out 1089 ms 27984 KB Time limit exceeded
11 Execution timed out 1059 ms 27856 KB Time limit exceeded
12 Execution timed out 1089 ms 26208 KB Time limit exceeded
13 Execution timed out 1098 ms 31608 KB Time limit exceeded
14 Correct 526 ms 23792 KB Output is correct

Subtask #4
2.22222222222 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1096 ms 27888 KB Time limit exceeded
2 Execution timed out 1022 ms 25712 KB Time limit exceeded
3 Correct 510 ms 31348 KB Output is correct
4 Execution timed out 1098 ms 28016 KB Time limit exceeded
5 Execution timed out 1067 ms 27760 KB Time limit exceeded
6 Correct 789 ms 27760 KB Output is correct
7 Execution timed out 1038 ms 25712 KB Time limit exceeded
8 Correct 556 ms 31220 KB Output is correct
9 Correct 405 ms 23536 KB Output is correct