oj.uz

Submission #850164

# Submission time Handle Problem Language Result Execution time Memory
850164 2023-09-15T22:48:11 Z NK_ Ball Machine (BOI13_ballmachine) C++17
100 / 100
 161 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 1 ms 344 KB Output is correct
2 Correct 59 ms 11464 KB Output is correct
3 Correct 41 ms 11720 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 4 ms 1116 KB Output is correct
10 Correct 13 ms 3160 KB Output is correct
11 Correct 58 ms 11536 KB Output is correct
12 Correct 40 ms 11720 KB Output is correct
13 Correct 74 ms 11524 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5844 KB Output is correct
2 Correct 111 ms 22476 KB Output is correct
3 Correct 59 ms 17100 KB Output is correct
4 Correct 37 ms 7124 KB Output is correct
5 Correct 38 ms 7116 KB Output is correct
6 Correct 37 ms 7116 KB Output is correct
7 Correct 35 ms 5844 KB Output is correct
8 Correct 23 ms 5840 KB Output is correct
9 Correct 96 ms 22988 KB Output is correct
10 Correct 121 ms 22476 KB Output is correct
11 Correct 124 ms 22436 KB Output is correct
12 Correct 98 ms 19652 KB Output is correct
13 Correct 78 ms 25292 KB Output is correct
14 Correct 53 ms 17176 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 11724 KB Output is correct
2 Correct 123 ms 20380 KB Output is correct
3 Correct 96 ms 22980 KB Output is correct
4 Correct 91 ms 18376 KB Output is correct
5 Correct 84 ms 18128 KB Output is correct
6 Correct 81 ms 18128 KB Output is correct
7 Correct 73 ms 16336 KB Output is correct
8 Correct 91 ms 22980 KB Output is correct
9 Correct 116 ms 22976 KB Output is correct
10 Correct 145 ms 22788 KB Output is correct
11 Correct 124 ms 22732 KB Output is correct
12 Correct 105 ms 20236 KB Output is correct
13 Correct 161 ms 28620 KB Output is correct
14 Correct 69 ms 17096 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 23240 KB Output is correct
2 Correct 111 ms 20344 KB Output is correct
3 Correct 123 ms 28452 KB Output is correct
4 Correct 129 ms 23240 KB Output is correct
5 Correct 136 ms 22984 KB Output is correct
6 Correct 98 ms 22472 KB Output is correct
7 Correct 113 ms 20256 KB Output is correct
8 Correct 88 ms 28620 KB Output is correct
9 Correct 54 ms 17096 KB Output is correct