제출 #929030

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
929030		NK_	Džumbus (COCI19_dzumbus)	C++17	110 / 110	41 ms	11348 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
		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 / 20
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30