oj.uz

Submission #922901

# Submission time Handle Problem Language Result Execution time Memory
922901 2024-02-06T09:07:00 Z MinaRagy06 Džumbus (COCI19_dzumbus) C++17
110 / 110
 786 ms 41444 KB 
#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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 32080 KB Output is correct
2 Correct 613 ms 32080 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 32080 KB Output is correct
2 Correct 613 ms 32080 KB Output is correct
3 Correct 786 ms 33900 KB Output is correct
4 Correct 456 ms 34280 KB Output is correct
5 Correct 494 ms 33716 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5460 KB Output is correct
2 Correct 28 ms 5200 KB Output is correct
3 Correct 45 ms 5204 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 32080 KB Output is correct
2 Correct 613 ms 32080 KB Output is correct
3 Correct 786 ms 33900 KB Output is correct
4 Correct 456 ms 34280 KB Output is correct
5 Correct 494 ms 33716 KB Output is correct
6 Correct 26 ms 5460 KB Output is correct
7 Correct 28 ms 5200 KB Output is correct
8 Correct 45 ms 5204 KB Output is correct
9 Correct 67 ms 34204 KB Output is correct
10 Correct 72 ms 37716 KB Output is correct
11 Correct 171 ms 41444 KB Output is correct