Submission #922901

#	Time	Username	Problem	Language	Result	Execution time	Memory
922901		MinaRagy06	Džumbus (COCI19_dzumbus)	C++17	110 / 110	786 ms	41444 KiB

dzumbus

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 1005;
vector<int> adj[N], tempadj[N];
bool vis[N];
void build(int i, int par) {
	vis[i] = 1;
	vector<int> newadj;
	for (auto nxt : tempadj[i]) {
		if (nxt == par) continue;
		build(nxt, i);
		newadj.push_back(nxt);
	}
	tempadj[i] = newadj;
}
int sz[N], tempsz[N], st[N], t;
void build2(int i) {
	st[i] = t++;
	tempsz[i] = 1;
	for (auto nxt : tempadj[i]) {
		build2(nxt);
		tempsz[i] += tempsz[nxt];
	}
}
ll a[N], dp[N][N][2][2];
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n, m;
	cin >> n >> m;
	ll tempa[n + 1];
	for (int i = 1; i <= n; i++) {
		cin >> tempa[i];
	}
	for (int i = 0, u, v; i < m; i++) {
		cin >> u >> v;
		tempadj[u].push_back(v);
		tempadj[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		if (vis[i]) continue;
		build(i, 0);
		tempadj[0].push_back(i);
	}
	tempa[0] = 1e18;
	build2(0);
	for (int i = 0; i <= n; i++) {
		adj[st[i]] = tempadj[i];
		for (auto &nxt : adj[st[i]]) nxt = st[nxt];
	}
	for (int i = 0; i <= n; i++) {
		a[st[i]] = tempa[i];
		sz[st[i]] = tempsz[i];
	}
	for (int i = n; i >= 0; i--) {
		for (int f = 0; f < 2; f++) {
			m = adj[i].size();
			ll dp2[m + 1][sz[i] + 1][3]{};
			for (int l = 0; l <= sz[i]; l++) dp2[m][l][0] = dp2[m][l][1] = 1e18;
			dp2[m][0][0] = 0;
			int s = 0;
			for (int k = m - 1; k >= 0; k--) {
				s += sz[adj[i][k]];
				for (int l = 0; l <= s; l++) {
					for (int f2 = 0; f2 < 2; f2++) {
						dp2[k][l][f2] = 1e18;
						for (int o = max(0, l + sz[adj[i][k]] - s); o <= sz[adj[i][k]]; o++) {
							dp2[k][l][f2] = min(dp2[k][l][f2], dp2[k + 1][l - o][f2] + dp[adj[i][k]][o][0][f]);
							dp2[k][l][f2] = min(dp2[k][l][f2], dp2[k + 1][l - o][0] + dp[adj[i][k]][o][1][f]);
						}
					}
				}
				for (int l = s + 1; l <= sz[i]; l++) {
					for (int f2 = 0; f2 < 2; f2++) {
						dp2[k][l][f2] = 1e18;
					}
				}
			}
			for (int j = 0; j <= sz[i]; j++) {
				for (int par = 0; par < 2; par++) {
					dp[i][j][f][par] = 1e18;
					if (f) {
						if (j == 0) continue;
						if (par) {
							dp[i][j][f][par] = min(dp[i][j][f][par], dp2[0][j - 1][0] + a[i]);
						} else {
							dp[i][j][f][par] = min(dp[i][j][f][par], dp2[0][j - 1][1] + a[i]);
						}
					} else {
						dp[i][j][f][par] = dp2[0][j][0];
					}
				}
			}
			for (int j = sz[i] + 1; j <= n; j++) {
				for (int par = 0; par < 2; par++) {
					dp[i][j][f][par] = 1e18;
				}
			}
		}
	}
	int q;
	cin >> q;
	while (q--) {
		ll s;
		cin >> s;
		for (int i = n; i >= 0; i--) {
			if (dp[0][i][0][0] <= s) {
				cout << i << '\n';
				break;
			}
		}
	}
	return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30