oj.uz

Submission #957296

# Submission time Handle Problem Language Result Execution time Memory
957296 2024-04-03T12:25:21 Z Mizo_Compiler Džumbus (COCI19_dzumbus) C++17
110 / 110
 45 ms 14164 KB 
#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(y, dp[v][2]), 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 = 2, r = n, ans = 0;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if ((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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8536 KB Output is correct
2 Correct 14 ms 11556 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8536 KB Output is correct
2 Correct 14 ms 11556 KB Output is correct
3 Correct 44 ms 14164 KB Output is correct
4 Correct 44 ms 12108 KB Output is correct
5 Correct 44 ms 10580 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1504 KB Output is correct
2 Correct 28 ms 2316 KB Output is correct
3 Correct 31 ms 2816 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 8536 KB Output is correct
2 Correct 14 ms 11556 KB Output is correct
3 Correct 44 ms 14164 KB Output is correct
4 Correct 44 ms 12108 KB Output is correct
5 Correct 44 ms 10580 KB Output is correct
6 Correct 28 ms 1504 KB Output is correct
7 Correct 28 ms 2316 KB Output is correct
8 Correct 31 ms 2816 KB Output is correct
9 Correct 36 ms 3408 KB Output is correct
10 Correct 45 ms 4020 KB Output is correct
11 Correct 42 ms 3412 KB Output is correct