Submission #928729

#	Time	Username	Problem	Language	Result	Execution time	Memory
928729		NK_	Džumbus (COCI19_dzumbus)	C++17	0 / 110	27 ms	7260 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 = 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
		V<vl> ndp(3, vl(sub[u] + 1, INFL));

		// 2 -> 0
		// 1 -> 0 / 1 / 2 (on)
		// 0 -> 0 / 1 / 2 (off)
		for(int tu = 0; tu < 3; tu++) for(int x = 0; x < sz(dp[u][tu]); x++) {
			if (dp[u][tu][x] == INFL) continue;
			// cout << tu << " " << x << " <U> " << dp[u][tu][x] << endl;

			ndp[tu][x] = min(ndp[tu][x], dp[u][tu][x]);

			for(int tv = 0; tv < 3; tv++) for(int y = 0; y < sz(dp[v][tv]); y++) {	
				if (dp[v][tv][y] == INFL) continue;

				// cout << tv << " " << y << " <V> " << dp[v][tv][y] << endl;

				// if its 2 then it must combine with a state that has the root on
				int t = (tu == 2 ? (tv != 0) : tu);
				ll ex = (t ? (tu == 2) * A[u] + (tv == 2) * A[v] : 0);
				int amt = (t ? (tu == 2) + (tv == 2) : 0);

				// cout << t << " " << x + y + amt << " " << dp[u][tu][x] + dp[v][tv][y] + ex << endl;
				// cout << endl;
				ndp[t][x + y + amt] = min(ndp[t][x + y + amt], dp[u][tu][x] + dp[v][tv][y] + ex);
			}
		}

		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] = {0};
		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] = dp[N][2] = {INFL};
	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];
	// 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[2]) cout << 0 << nl;
		else {
			int ans = upper_bound(begin(ANS) + 2, 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