oj.uz

Submission #850162

# Submission time Handle Problem Language Result Execution time Memory
850162 2023-09-15T22:44:55 Z NK_ Ball Machine (BOI13_ballmachine) C++17
100 / 100
 160 ms 29128 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), dep(N);
	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; dep[v] = dep[u] + 1; gen(v);
			mn[u] = min(mn[v], mn[u]);
		}

	};

	dep[R] = 0; 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();
 				// cout << "ADD: " << u << endl;
 				C[u] = 1; lst = u; 
 			}
 			cout << lst + 1 << nl;
 		} else {
 			int u; cin >> u; --u;
 			int d = dep[u];

 			assert(C[u] == 1);
 			for(int i = LG-1; i >= 0; i--) {
 				// cout << u << " " << i << endl;
 				// cout << up[u][i] << endl;
 				if (C[up[u][i]]) u = up[u][i];
 			}


 			// cout << "REM: " << u << endl;

 			C[u] = 0; if (u != N) W.push(mp(ord[u], u));
 			cout << d - dep[u] << 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 348 KB Output is correct
2 Correct 72 ms 11872 KB Output is correct
3 Correct 43 ms 12136 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 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 13 ms 3400 KB Output is correct
11 Correct 61 ms 11812 KB Output is correct
12 Correct 41 ms 11988 KB Output is correct
13 Correct 55 ms 11868 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5760 KB Output is correct
2 Correct 102 ms 22784 KB Output is correct
3 Correct 64 ms 17528 KB Output is correct
4 Correct 39 ms 7384 KB Output is correct
5 Correct 41 ms 7128 KB Output is correct
6 Correct 36 ms 7288 KB Output is correct
7 Correct 36 ms 6100 KB Output is correct
8 Correct 22 ms 5848 KB Output is correct
9 Correct 115 ms 23660 KB Output is correct
10 Correct 122 ms 22732 KB Output is correct
11 Correct 109 ms 22732 KB Output is correct
12 Correct 115 ms 19940 KB Output is correct
13 Correct 103 ms 25608 KB Output is correct
14 Correct 65 ms 17680 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 12108 KB Output is correct
2 Correct 127 ms 20728 KB Output is correct
3 Correct 107 ms 23180 KB Output is correct
4 Correct 76 ms 18884 KB Output is correct
5 Correct 79 ms 18408 KB Output is correct
6 Correct 81 ms 18380 KB Output is correct
7 Correct 95 ms 16596 KB Output is correct
8 Correct 135 ms 23284 KB Output is correct
9 Correct 119 ms 23432 KB Output is correct
10 Correct 131 ms 23036 KB Output is correct
11 Correct 120 ms 22904 KB Output is correct
12 Correct 141 ms 20764 KB Output is correct
13 Correct 160 ms 29128 KB Output is correct
14 Correct 76 ms 17500 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 23552 KB Output is correct
2 Correct 143 ms 20904 KB Output is correct
3 Correct 98 ms 28876 KB Output is correct
4 Correct 138 ms 23524 KB Output is correct
5 Correct 125 ms 23120 KB Output is correct
6 Correct 123 ms 23124 KB Output is correct
7 Correct 119 ms 20680 KB Output is correct
8 Correct 128 ms 28836 KB Output is correct
9 Correct 55 ms 17604 KB Output is correct