oj.uz

Submission #850163

# Submission time Handle Problem Language Result Execution time Memory
850163 2023-09-15T22:47:01 Z NK_ Ball Machine (BOI13_ballmachine) C++17
100 / 100
 165 ms 28620 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
template<class T> using pq = priority_queue<T, V<T>, greater<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 18;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int N, Q; cin >> N >> Q;

	int R = -1;
	vi P(N);
	V<vi> chd(N); for(int i = 0; i < N; i++) {
		int p; cin >> p; --p;
		if (p != -1) chd[p].pb(i), P[i] = p;
		else R = i, P[i] = -1;
	}

	vi mn(N, MOD);
	V<vi> up(N+1, vi(LG, N));
	function<void(int)> gen = [&](int u) {
		for(int i = 1; i < LG; i++) up[u][i] = up[up[u][i-1]][i-1];
		mn[u] = u;
	
		for(auto& v : chd[u]) {
			up[v][0] = u; gen(v);
			mn[u] = min(mn[v], mn[u]);
		}
	};
	
	gen(R);

	vi deg(N); for(int i = 0; i < N; i++) deg[i] = sz(chd[i]);

	vi ord(N); int cur = 0;

	function<void(int)> dfs = [&](int u) {
		sort(begin(chd[u]), end(chd[u]), [&](int x, int y) {
			return mn[x] < mn[y];
		});

		for(auto v : chd[u]) dfs(v);

		ord[u] = cur++;
	};
	dfs(R);
 		
 	pq<pi> W; for(int i = 0; i < N; i++) W.push(mp(ord[i], i));

 	vi C(N+1); // C[i] = 0 (off) / 1 (on)
 	for(int t = 0; t < Q; t++) {
 		int type; cin >> type;
 		if (type == 1) {
 			int k; cin >> k;
 			int lst = -1;
 			while(k--) {
 				int u = W.top().s; W.pop();
 				C[u] = 1; lst = u; 
 			}
 			cout << lst + 1 << nl;
 		} else {
 			int u; cin >> u; --u;

 			int ans = 0;
 			for(int i = LG-1; i >= 0; i--) {
 				if (C[up[u][i]]) { u = up[u][i]; ans += (1 << i); }
 			}


 			C[u] = 0; W.push(mp(ord[u], u));
 			cout << ans << nl;
 		}
 	}

 	// for(int i = 0; i < N; i++) cout << i << " " << C[i] << endl;


	exit(0-0);
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 63 ms 11604 KB Output is correct
3 Correct 41 ms 11720 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 4 ms 1116 KB Output is correct
10 Correct 12 ms 3164 KB Output is correct
11 Correct 60 ms 11544 KB Output is correct
12 Correct 41 ms 11844 KB Output is correct
13 Correct 55 ms 11464 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5784 KB Output is correct
2 Correct 129 ms 22408 KB Output is correct
3 Correct 59 ms 17156 KB Output is correct
4 Correct 48 ms 7124 KB Output is correct
5 Correct 37 ms 7116 KB Output is correct
6 Correct 44 ms 7136 KB Output is correct
7 Correct 39 ms 5844 KB Output is correct
8 Correct 22 ms 5848 KB Output is correct
9 Correct 114 ms 22920 KB Output is correct
10 Correct 127 ms 22676 KB Output is correct
11 Correct 121 ms 22728 KB Output is correct
12 Correct 116 ms 19656 KB Output is correct
13 Correct 80 ms 25188 KB Output is correct
14 Correct 54 ms 17096 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 11680 KB Output is correct
2 Correct 116 ms 20168 KB Output is correct
3 Correct 105 ms 22908 KB Output is correct
4 Correct 90 ms 18516 KB Output is correct
5 Correct 95 ms 18400 KB Output is correct
6 Correct 79 ms 18132 KB Output is correct
7 Correct 69 ms 16336 KB Output is correct
8 Correct 97 ms 22984 KB Output is correct
9 Correct 130 ms 23096 KB Output is correct
10 Correct 115 ms 22712 KB Output is correct
11 Correct 110 ms 22636 KB Output is correct
12 Correct 132 ms 20168 KB Output is correct
13 Correct 165 ms 28612 KB Output is correct
14 Correct 77 ms 17100 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 23092 KB Output is correct
2 Correct 136 ms 20268 KB Output is correct
3 Correct 92 ms 28436 KB Output is correct
4 Correct 145 ms 23148 KB Output is correct
5 Correct 165 ms 22736 KB Output is correct
6 Correct 132 ms 22476 KB Output is correct
7 Correct 138 ms 20348 KB Output is correct
8 Correct 128 ms 28620 KB Output is correct
9 Correct 66 ms 17100 KB Output is correct