oj.uz

Submission #929030

# Submission time Handle Problem Language Result Execution time Memory
929030 2024-02-17T13:48:00 Z NK_ Džumbus (COCI19_dzumbus) C++17
110 / 110
 41 ms 11348 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 sz(x) int(x.size())

using ll = long long;
template<class T> using V = vector<T>;
using vi = V<int>;
using vl = V<ll>;

const ll INFL = 1e15;

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

	vl A(N); for(auto& x : A) cin >> x;
	A.pb(INFL);

	V<V<vl>> dp(N + 1, V<vl>(3)); V<vi> adj(N);
	for(int i = 0; i < M; i++) {	
		int u, v; cin >> u >> v; --u, --v;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	vi vis(N), sub(N + 1);
	auto cmb = [&](int u, int v) { // v into v
		int M = sub[u] + sub[v] + 1; 
		V<vl> ndp(3, vl(M, INFL));

		// 2 -> 0
		// 1 -> 0 / 1 / 2 (on)
		// 0 -> 0 / 1 / 2 (off)
		for(int x = 0; x <= sub[u]; x++) {
			for(int y = 0; y <= sub[v]; y++) {		
				// 0 0
				ndp[0][x + y] = min(ndp[0][x + y], dp[u][0][x] + dp[v][0][y]);

				// 0 1
				ndp[0][x + y] = min(ndp[0][x + y], dp[u][0][x] + dp[v][1][y]);

				// 0 2
				ndp[0][x + y] = min(ndp[0][x + y], dp[u][0][x] + dp[v][2][y]);

				// 1 0
				ndp[1][x + y] = min(ndp[1][x + y], dp[u][1][x] + dp[v][0][y]);

				// 1 1
				ndp[1][x + y] = min(ndp[1][x + y], dp[u][1][x] + dp[v][1][y]);

				// 1 2 (2 becomes a 1)
				if (x + y + 1 < M) ndp[1][x + y + 1] = min(ndp[1][x + y + 1], dp[u][1][x] + dp[v][2][y]);

				// 2 0
				ndp[2][x + y] = min(ndp[2][x + y], dp[u][2][x] + dp[v][0][y]);

				// 2 1 (2 becomes a 1)
				if (x + y + 1 < M) ndp[1][x + y + 1] = min(ndp[1][x + y + 1], dp[u][2][x] + dp[v][1][y]);

				// 2 2 (2s become 1s)
				if (x + y + 2 < M) ndp[1][x + y + 2] = min(ndp[1][x + y + 2], dp[u][2][x] + dp[v][2][y]);
			}
		}

		sub[u] += sub[v];
		dp[u].swap(ndp);
	};

	function<void(int, int)> dfs = [&](int u, int p) {
		vis[u] = 1; sub[u] = 1; 
		dp[u][0] = {0, INFL}, dp[u][1] = {INFL, INFL}, dp[u][2] = {A[u], INFL};
		for(auto& v : adj[u]) if (v != p) {
			dfs(v, u); 
			cmb(u, v);
		}

		// cout << "U: " << u << endl;
		// for(int t = 0; t < 3; t++) {
		// 	for(int i = 0; i < sz(dp[u][t]); i++) {
		// 		cout << t << " " << i << " ===> " << dp[u][t][i] << endl;
		// 	}
		// 	cout << endl;
		// }
		// cout << endl << endl;
	};

	sub[N] = 1; dp[N][0] = {0, INFL}, dp[N][1] = {INFL, INFL}, dp[N][2] = {A[N], INFL};
	for(int i = 0; i < N; i++) if (!vis[i]) {
		dfs(i, -1); 
		cmb(N, i);
	}

	vl ANS = dp[N][0]; ANS.pb(INFL);
	ANS.erase(begin(ANS)); ANS.erase(begin(ANS));
	for(int i = sz(ANS) - 2; i >= 0; i--) ANS[i] = min(ANS[i], ANS[i + 1]);

	// cout << "ANS: " << sz(ANS) << endl;
	// for(int i = 0; i < sz(ANS); i++) cout << i << " => " << ANS[i] << endl;

	int Q; cin >> Q;
	for(int q = 0; q < Q; q++) {
		int x; cin >> x;

		if (x < ANS.front()) cout << 0 << nl;
		else {
			int ans = upper_bound(begin(ANS), end(ANS), x) - begin(ANS);
			cout << ans + 1 << nl;
		}
	}






	exit(0-0);
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7256 KB Output is correct
2 Correct 9 ms 8284 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7256 KB Output is correct
2 Correct 9 ms 8284 KB Output is correct
3 Correct 35 ms 11348 KB Output is correct
4 Correct 41 ms 9808 KB Output is correct
5 Correct 34 ms 9040 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1116 KB Output is correct
2 Correct 24 ms 1104 KB Output is correct
3 Correct 27 ms 2652 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7256 KB Output is correct
2 Correct 9 ms 8284 KB Output is correct
3 Correct 35 ms 11348 KB Output is correct
4 Correct 41 ms 9808 KB Output is correct
5 Correct 34 ms 9040 KB Output is correct
6 Correct 25 ms 1116 KB Output is correct
7 Correct 24 ms 1104 KB Output is correct
8 Correct 27 ms 2652 KB Output is correct
9 Correct 34 ms 3412 KB Output is correct
10 Correct 36 ms 3400 KB Output is correct
11 Correct 37 ms 3240 KB Output is correct