Submission #1222499

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222499		TIN	Džumbus (COCI19_dzumbus)	C++20	110 / 110	54 ms	14296 KiB

dzumbus

#include <bits/stdc++.h>

using namespace std;

#define FNAME "DZUMBUS"

typedef long long ll;

const int N = 1005;
const ll oo = 1e18;

int n, m, q;
int d[N];
vector<int> adj[N];
vector<ll> dp[N][3];
bool visited[N];

void Task() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cout << fixed << setprecision(9);
	if (fopen(FNAME".inp","r")) {
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

void Input() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> d[i];
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
}

vector<ll> merging(vector<ll> a, const vector<ll>& b) {
	vector<ll> ret((int) a.size() + (int) b.size() - 1, oo);
	for (int i = 0; i < (int) a.size(); i++)
		for (int j = 0; j < (int) b.size(); j++)
			ret[i + j] = min(ret[i + j], a[i] + b[j]);
	return ret;
}

vector<ll> minimizing(vector<ll> a, const vector<ll>& b) {
	while ((int) a.size() < (int) b.size()) a.push_back(oo);
	for (int i = 0; i < (int) b.size(); i++) a[i] = min(a[i], b[i]);
	return a;
}

void DFS(int u, int par) {
	visited[u] = true;
	dp[u][0] = {0}; dp[u][1] = {oo, d[u]};
	for (int v : adj[u]) {
		if (v ^ par) {
			DFS(v, u);
			dp[u][0] = merging(dp[u][0], minimizing(dp[v][0], dp[v][2]));
			dp[u][2] = minimizing(merging(dp[u][2], minimizing(minimizing(dp[v][0], dp[v][1]), dp[v][2])), merging(dp[u][1], minimizing(dp[v][1], dp[v][2])));
			dp[u][1] = merging(dp[u][1], dp[v][0]);
		}
	}
}

void solve() {
	vector<ll> res = { 0 };
	memset(visited, false, sizeof(visited));
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {
			DFS(i, i);
			res = merging(res, minimizing(dp[i][0], dp[i][2]));
		}
	}
	for (int i = (int) res.size() - 2; i >= 0; i--) res[i] = min(res[i], res[i + 1]);
	cin >> q;
	while (q--) {
		int s; cin >> s;
		int L = -1, R = (int) res.size() - 1;
		while (L < R) {
			int M = (L + R + 1) / 2;
			if (res[M] <= s) L = M;
			else R = M - 1;
		}
		cout << L << '\n';
	}
}

void Solve() {
	//Your Code
	Input();
	solve();
}

int main() {
	Task();
	Solve();
	cerr << "\nTime run: " << 1000*clock()/CLOCKS_PER_SEC << "ms";
	return 37^37;
}

Compilation message (stderr)

dzumbus.cpp: In function 'void Task()':
dzumbus.cpp:23:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:24:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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