Submission #491452

#	Time	Username	Problem	Language	Result	Execution time	Memory
491452		Nimbostratus	Džumbus (COCI19_dzumbus)	C++17	0 / 110	250 ms	10904 KiB

dzumbus

#include "bits/stdc++.h"
#define endl '\n'
#define int long long
const int maxn = 1005;
const int inf = 1e13;
const int mod = 1e9 + 7;
using namespace std;
using lint = long long;
using pii = pair<int,int>;

int n, m, q;
int s[maxn];
vector<int> adj[maxn];
int sz[maxn];
int dp[maxn][maxn][3];
int now[maxn][3], prv[maxn][3];
int p[maxn];
int tmp[maxn], ans[maxn];

void dfs(int u) {
	sz[u] = 1;
	for(int v : adj[u]) {
		if(v == p[u])
			continue;
		p[v] = u;
		dfs(v);
		sz[u] += sz[v];
	}
	for(int k = 0; k <= sz[u]; k++)
		now[k][0] = now[k][1] = now[k][2] = inf;
	now[0][0] = 0;
	now[0][1] = s[u];
	now[0][2] = inf;
	for(int v : adj[u]) {
		if(v == p[u])
			continue;
		for(int k = 0; k <= sz[u]; k++) {
			prv[k][0] = now[k][0]; 
			prv[k][1] = now[k][1]; 
			prv[k][2] = now[k][2];
			now[k][0] = now[k][1] = now[k][2] = inf;
		}
		for(int k = 0; k <= sz[u]; k++)
			for(int x = 0; x <= min(sz[v], k); x++) {
				int r0 = min({dp[v][x][0], dp[v][x][1], dp[v][x][2]}) + prv[k - x][0];
				int r1 = dp[v][x][0] + prv[k - x][1];
				int r2 = min({
					k - x >= 2 ? dp[v][x][1] + prv[k - x - 2][1] : inf,
					k - x >= 1 ? dp[v][x][1] + prv[k - x - 1][2] : inf,
					dp[v][x][0] + prv[k - x][2],
					dp[v][x][2] + prv[k - x][2]

				});
				now[k][0] = min(now[k][0], r0);
				now[k][1] = min(now[k][1], r1);
				now[k][2] = min(now[k][2], r2);
			}
	}
	for(int k = 0; k <= sz[u]; k++) {
		dp[u][k][0] = now[k][0];
		dp[u][k][1] = now[k][1];
		dp[u][k][2] = now[k][2];
	}
}

void precomp() {
	for(int k = 1; k <= n; k++)
		ans[k] = inf;
	ans[0] = 0;
	for(int v = 1; v <= n; v++) {
		if(p[v])
			continue;
		dfs(v);
		for(int k = 0; k <= n; k++) {
			tmp[k] = ans[k];
			ans[k] = inf;
		}
		for(int k = 0; k <= n; k++)
			for(int x = 0; x <= min(sz[v], k); x++) {
				int res = min({dp[v][x][0], dp[v][x][1], dp[v][x][2]}) + tmp[k - x];
				ans[k] = min(ans[k], res);
			}
	}
}

int solve(int x) {
	if(n < 2)
		return 0;
	int l = 2, r = n, mid;
	while(l < r - 1) {
		mid = (l + r) / 2;
		if(ans[mid] > x)
			r = mid - 1;
		else
			l = mid;
	}
	return ans[r] > x ? (ans[l] > x ? 0 : l) : r;
}

signed main() {
	#ifdef Local
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	#endif
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
		cin >> s[i];
	for(int i = 0, x, y; i < m; i++) {
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	precomp();
	cin >> q;
	while(q--) {
		int x;
		cin >> x;
		cout << solve(x) << endl;
	}
}

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