oj.uz

Submission #922878

# Submission time Handle Problem Language Result Execution time Memory
922878 2024-02-06T08:43:19 Z MinaRagy06 Džumbus (COCI19_dzumbus) C++17
30 / 110
 1000 ms 7328 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 st[N], t;
void build2(int i) {
	st[i] = t++;
	for (auto nxt : tempadj[i]) {
		build2(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];
	}
	for (int i = n; i >= 0; i--) {
		for (int f = 0; f < 2; f++) {
			int sz = adj[i].size();
			ll dp2[sz + 1][n + 1][3]{};
			for (int l = 0; l <= n; l++) dp2[sz][l][0] = dp2[sz][l][1] = 1e18;
			dp2[sz][0][0] = 0;
			for (int k = sz - 1; k >= 0; k--) {
				for (int l = 0; l <= n; l++) {
					for (int f2 = 0; f2 < 3; f2++) {
						dp2[k][l][f2] = 1e18;
						for (int o = 0; o <= l; 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 j = 0; j <= n; 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];
					}
				}
			}
		}
	}
	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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1039 ms 7328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1039 ms 7328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5468 KB Output is correct
2 Correct 35 ms 5200 KB Output is correct
3 Correct 50 ms 4908 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1039 ms 7328 KB Time limit exceeded
2 Halted 0 ms 0 KB -