Submission #957290

#	Time	Username	Problem	Language	Result	Execution time	Memory
957290		Mizo_Compiler	Džumbus (COCI19_dzumbus)	C++17	0 / 110	29 ms	8536 KiB

dzumbus

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
#define pb push_back
#define sz(x) int32_t(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
const int N = 1001;
const ll inf = 1e18+1;
ll d[N];
vector<ll> dp[N][3];
int n, m;
vector<int> adj[N];

vector<ll> comb(vector<ll> a, vector<ll> b) {
	vector<ll> ret(sz(a) + sz(b) - 1, inf);
	for (int i = 0; i < sz(a); i++) {
		for (int j = 0; j < sz(b); j++) {
			ret[i+j] = min(ret[i+j], a[i] + b[j]);
		}
	}
	return ret;
}

vector<ll> minz(vector<ll> a, vector<ll> b) {
	vector<ll> ret(max(sz(a), sz(b)));
	for (int i = 0; i < sz(ret); i++) {
		ret[i] = min((i < sz(a) ? a[i] : inf), (i < sz(b) ? b[i] : inf));
	}
	return ret;
}

vector<ll> add(vector<ll> a, ll val) {
	vector<ll> ret = a;
	for (auto &i : ret)i = min(inf, i+val);
	return ret;
}

vector<ll> shift(vector<ll> a, int x) {
	vector<ll> ret = a;
	while (x--)ret.insert(ret.begin(), inf);
	return ret;
}
//N,Y   W,N    Y,Y
void dfs(int u, int p) {
	dp[u][0] = dp[u][1] = {0};
	dp[u][2] = {inf, d[u]};
	vector<ll> x = {0}, y = {};
	bool f = false;
	for (auto &v : adj[u]) {
		if (v == p)continue;
		dfs(v, u);
		vector<ll> c = dp[u][0], c2 = dp[u][1], c3 = dp[u][2];
		dp[u][1] = minz(comb(c2, dp[v][1]), comb(c2, dp[v][0]));
		dp[u][2] = minz(comb(c3, dp[v][2]), comb(c3, dp[v][1]));
		dp[u][0] = minz(comb(x, add(shift(dp[v][2], 1), d[u])), minz(comb(c, dp[v][1]), comb(y, dp[v][2])));
		if (!f)y = add(shift(dp[v][2], 1), d[u]);
		else y = minz(comb(x, add(shift(dp[v][2], 1), d[u])), comb(y, dp[v][1]));
		x = comb(x, dp[v][1]);
		f = true;
	}
}

bool vis[N];

void dfs2(int u) {
	vis[u] = true;
	for (auto &v : adj[u]) {
		if (!vis[v]) {
			dfs2(v);
		}
	}
}

signed main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
    cin >> n >> m;
	d[0] = inf;
	for (int i = 1; i <= n; i++) {
		cin >> d[i];
	}
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].pb(v);
		adj[v].pb(u);
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			adj[0].pb(i);
			dfs2(i);
		}
	}
	dfs(0, 0);
	int q;
	cin >> q;
	while (q--) {
		ll x;
		cin >> x;
		int l = 1, r = n, ans = 0;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (min((sz(dp[0][0]) > mid ? dp[0][0][mid] : inf), (sz(dp[0][1]) > mid ? dp[0][1][mid] : inf)) <= x) {
				ans = mid;
				l = mid+1;
			} else {
				r = mid-1;
			}
		}
		cout << ans << "\n";
	}
}

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