oj.uz

Submission #850157

# Submission time Handle Problem Language Result Execution time Memory
850157 2023-09-15T22:12:27 Z NK_ Ball Machine (BOI13_ballmachine) C++17
20.9524 / 100
 148 ms 45640 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);

	pq<pi> q; for(int i = 0; i < N; i++) if (deg[i] == 0) {
		q.push(mp(mn[i], i));
	}

	int cur = 0;
	while(sz(q)) {
		int u = q.top().s; q.pop();

		// cout << u << " " << cur << endl;
		ord[u] = cur++;

		if (P[u] != -1) {
			// cout << P[u] << endl;
			// cout << deg[P[u]] << endl;
			deg[P[u]]--; 
			if (deg[P[u]] == 0) q.push(mp(mn[P[u]], P[u]));
		}
	}
 		
 	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
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 6
2 Runtime error 40 ms 23888 KB Execution killed with signal 6
3 Runtime error 35 ms 23896 KB Execution killed with signal 6
4 Runtime error 1 ms 604 KB Execution killed with signal 6
5 Runtime error 1 ms 604 KB Execution killed with signal 6
6 Runtime error 1 ms 860 KB Execution killed with signal 6
7 Runtime error 1 ms 860 KB Execution killed with signal 6
8 Runtime error 1 ms 860 KB Execution killed with signal 6
9 Runtime error 3 ms 1880 KB Execution killed with signal 6
10 Runtime error 10 ms 6560 KB Execution killed with signal 6
11 Runtime error 46 ms 23888 KB Execution killed with signal 6
12 Runtime error 36 ms 24044 KB Execution killed with signal 6
13 Runtime error 36 ms 24048 KB Execution killed with signal 6

Subtask #2
10.7142857143 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5592 KB Output is correct
2 Runtime error 120 ms 44596 KB Execution killed with signal 6
3 Correct 58 ms 17992 KB Output is correct
4 Runtime error 23 ms 14104 KB Execution killed with signal 6
5 Runtime error 20 ms 13784 KB Execution killed with signal 6
6 Runtime error 19 ms 13724 KB Execution killed with signal 6
7 Runtime error 17 ms 11732 KB Execution killed with signal 6
8 Correct 22 ms 5592 KB Output is correct
9 Runtime error 101 ms 45500 KB Execution killed with signal 6
10 Runtime error 113 ms 44684 KB Execution killed with signal 6
11 Runtime error 89 ms 44828 KB Execution killed with signal 6
12 Runtime error 108 ms 39972 KB Execution killed with signal 6
13 Correct 84 ms 24272 KB Output is correct
14 Correct 63 ms 17988 KB Output is correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 49 ms 22988 KB Execution killed with signal 6
2 Runtime error 88 ms 40828 KB Execution killed with signal 6
3 Correct 104 ms 21988 KB Output is correct
4 Runtime error 65 ms 36424 KB Execution killed with signal 6
5 Runtime error 83 ms 35924 KB Execution killed with signal 6
6 Runtime error 66 ms 36040 KB Execution killed with signal 6
7 Runtime error 75 ms 32716 KB Execution killed with signal 6
8 Correct 97 ms 22076 KB Output is correct
9 Runtime error 134 ms 45640 KB Execution killed with signal 6
10 Runtime error 133 ms 45104 KB Execution killed with signal 6
11 Runtime error 110 ms 44804 KB Execution killed with signal 6
12 Runtime error 99 ms 40900 KB Execution killed with signal 6
13 Correct 148 ms 27636 KB Output is correct
14 Runtime error 76 ms 36136 KB Execution killed with signal 6

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 88 ms 45384 KB Execution killed with signal 6
2 Runtime error 101 ms 40780 KB Execution killed with signal 6
3 Correct 103 ms 27404 KB Output is correct
4 Runtime error 82 ms 45380 KB Execution killed with signal 6
5 Runtime error 104 ms 44696 KB Execution killed with signal 6
6 Runtime error 91 ms 44876 KB Execution killed with signal 6
7 Runtime error 93 ms 40796 KB Execution killed with signal 6
8 Correct 108 ms 27340 KB Output is correct
9 Correct 57 ms 17996 KB Output is correct