oj.uz

답안 #850152

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
850152 2023-09-15T21:51:42 Z NK_ Ball Machine (BOI13_ballmachine) C++17
0 / 100
 260 ms 28644 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));
	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]);
		}

	};

	up[R][0] = N, 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--) {
 				assert(sz(W));
 				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);
 					// assert(false);
 				}
 			}

 			C[u] = 0; if (u != N) 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
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Incorrect 160 ms 13244 KB Output isn't correct
3 Incorrect 121 ms 13244 KB Output isn't correct
4 Incorrect 1 ms 344 KB Output isn't correct
5 Incorrect 1 ms 344 KB Output isn't correct
6 Incorrect 2 ms 600 KB Output isn't correct
7 Incorrect 2 ms 600 KB Output isn't correct
8 Incorrect 2 ms 600 KB Output isn't correct
9 Incorrect 9 ms 1112 KB Output isn't correct
10 Incorrect 37 ms 3664 KB Output isn't correct
11 Incorrect 144 ms 13048 KB Output isn't correct
12 Incorrect 133 ms 13164 KB Output isn't correct
13 Incorrect 133 ms 13388 KB Output isn't correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 5580 KB Output isn't correct
2 Incorrect 246 ms 23632 KB Output isn't correct
3 Incorrect 180 ms 19012 KB Output isn't correct
4 Incorrect 73 ms 7952 KB Output isn't correct
5 Incorrect 74 ms 7628 KB Output isn't correct
6 Incorrect 75 ms 7736 KB Output isn't correct
7 Incorrect 70 ms 6604 KB Output isn't correct
8 Incorrect 42 ms 5720 KB Output isn't correct
9 Incorrect 219 ms 24084 KB Output isn't correct
10 Incorrect 235 ms 23844 KB Output isn't correct
11 Incorrect 234 ms 23956 KB Output isn't correct
12 Incorrect 220 ms 21496 KB Output isn't correct
13 Incorrect 179 ms 25036 KB Output isn't correct
14 Incorrect 180 ms 19016 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 117 ms 12248 KB Output isn't correct
2 Incorrect 244 ms 21844 KB Output isn't correct
3 Incorrect 206 ms 22744 KB Output isn't correct
4 Incorrect 177 ms 19180 KB Output isn't correct
5 Incorrect 181 ms 19028 KB Output isn't correct
6 Incorrect 173 ms 19016 KB Output isn't correct
7 Incorrect 167 ms 17224 KB Output isn't correct
8 Incorrect 176 ms 22768 KB Output isn't correct
9 Incorrect 237 ms 23620 KB Output isn't correct
10 Incorrect 250 ms 23552 KB Output isn't correct
11 Incorrect 246 ms 23752 KB Output isn't correct
12 Incorrect 248 ms 21832 KB Output isn't correct
13 Incorrect 260 ms 28644 KB Output isn't correct
14 Incorrect 198 ms 19268 KB Output isn't correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 249 ms 24364 KB Output isn't correct
2 Incorrect 237 ms 21720 KB Output isn't correct
3 Incorrect 229 ms 28036 KB Output isn't correct
4 Incorrect 231 ms 24256 KB Output isn't correct
5 Incorrect 239 ms 23644 KB Output isn't correct
6 Incorrect 218 ms 23624 KB Output isn't correct
7 Incorrect 258 ms 21896 KB Output isn't correct
8 Incorrect 205 ms 28108 KB Output isn't correct
9 Incorrect 187 ms 18972 KB Output isn't correct