Submission #444667

#	Time	Username	Problem	Language	Result	Execution time	Memory
444667		penguinhacker	Džumbus (COCI19_dzumbus)	C++14	0 / 110	58 ms	2636 KiB

dzumbus

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1001, INF=1e9+1;
int n, m, q, a[mxN];
vector<int> adj[mxN];
vector<ar<int, 2>> dp[mxN];
bool vis[mxN];

void smin(int& i, int j) {
	if (j<i)
		i=j;
}

void mrg(int u, int v) {
	vector<ar<int, 2>> r(dp[u].size()+dp[v].size()-1, {INF, INF});
	for (int i=0; i<dp[u].size(); ++i)
		for (int j=0; j<dp[v].size(); ++j) {
			smin(r[i+j][0], dp[u][i][0]+min(dp[v][j][0], dp[v][j][1]));
			smin(r[i+j][1], dp[u][i][1]+min(dp[v][j][0], dp[v][j][1]));
			if (j+1<dp[v].size())
				smin(r[i+j+1][1], min(INF, dp[u][i][1]+dp[v][j][0])+a[v]);
			if (i+1<dp[u].size()&&j+1<dp[v].size())
				smin(r[i+j+2][1], min(INF, dp[u][i][0]+dp[v][j][0])+min(INF, a[u]+a[v]));
		}
	swap(dp[u], r);
}

void dfs(int u, int p=0) {
	vis[u]=1;
	dp[u]={{0, INF}, {INF, INF}};
	for (int v : adj[u])
		if (!vis[v])
			dfs(v, u);
	mrg(p, u);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i=1; i<=n; ++i)
		cin >> a[i];
	for (int i=0; i<m; ++i) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	a[0]=INF;
	dp[0]={{0, INF}, {INF, INF}};
	for (int i=1; i<=n; ++i)
		if (!vis[i])
			dfs(i);
	assert(dp[0].size()==n+2);
	cin >> q;
	while(q--) {
		int x, ans=0;
		cin >> x;
		for (int i=1; i<=n; ++i)
			if (dp[0][i][0]<=x)
				ans=i;
		cout << ans << "\n";
	}
	return 0;
}

Compilation message (stderr)

dzumbus.cpp: In function 'void mrg(int, int)':
dzumbus.cpp:20:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for (int i=0; i<dp[u].size(); ++i)
      |                ~^~~~~~~~~~~~~
dzumbus.cpp:21:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for (int j=0; j<dp[v].size(); ++j) {
      |                 ~^~~~~~~~~~~~~
dzumbus.cpp:24:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |    if (j+1<dp[v].size())
      |        ~~~^~~~~~~~~~~~~
dzumbus.cpp:26:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |    if (i+1<dp[u].size()&&j+1<dp[v].size())
      |        ~~~^~~~~~~~~~~~~
dzumbus.cpp:26:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |    if (i+1<dp[u].size()&&j+1<dp[v].size())
      |                          ~~~^~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from dzumbus.cpp:1:
dzumbus.cpp: In function 'int main()':
dzumbus.cpp:58:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |  assert(dp[0].size()==n+2);
      |         ~~~~~~~~~~~~^~~~~

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