Submission #929024

#	Time	Username	Problem	Language	Result	Execution time	Memory
929024		NK_	Džumbus (COCI19_dzumbus)	C++17	0 / 110	25 ms	8284 KiB

dzumbus

// 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 = 1e16;

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
		V<vl> ndp(3, vl(sub[u] + 4, INFL));

		// 2 -> 0
		// 1 -> 0 / 1 / 2 (on)
		// 0 -> 0 / 1 / 2 (off)
		for(int x = 0; x < sz(dp[u][0]); x++) {
			for(int y = 0; y < sz(dp[v][0]); 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)
				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)
				ndp[1][x + y + 1] = min(ndp[1][x + y + 1], dp[u][2][x] + dp[v][1][y]);

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

		dp[u].swap(ndp);

		// 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;
		// }
	};

	function<void(int, int)> dfs = [&](int u, int p) {
		vis[u] = 1; sub[u] = 1; 
		dp[u][0] = {0}, dp[u][1] = {INFL}, dp[u][2] = {A[u]};
		for(auto& v : adj[u]) if (v != p) {
			dfs(v, u); 
			sub[u] += sub[v];
			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}, dp[N][1] = {INFL}, dp[N][2] = {A[N]};
	for(int i = 0; i < N; i++) if (!vis[i]) {
		dfs(i, -1); 
		sub[N] += sub[i];
		cmb(N, i);
	}

	vl ANS = dp[N][0];
	ANS.erase(begin(ANS)); ANS.erase(begin(ANS));

	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: 0 / 20
• Subtask 2: 0 / 30
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30