Submission #251552

#	Time	Username	Problem	Language	Result	Execution time	Memory
251552		MrRobot_28	Džumbus (COCI19_dzumbus)	C++17	110 / 110	82 ms	18936 KiB

dzumbus

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m;
vector <int> d;
vector <vector <int> > dp0, dp1, g;
vector <bool> used;
vector <int> sz;
vector <int> prev0, prev1;
int min(int a, int b)
{
	if(a < b)
	{
		return a;
	}
	return b;
}
void dfs(int v, int p = -1)
{
	if(v != n)
	{
		for(int i = 0; i < g[v].size(); i++)
		{
			int to = g[v][i];
			if(to != p)
			{
				dfs(to, v);
			}
		}
	}
	used[v] = true;
	int allsz = 0;
	dp0[v][0] = 0;
	sz[v] = 1;
	prev0[0] = 0;
	prev1[0] = 1e18;
	for(int i = 0; i < g[v].size(); i++)
	{
		int to = g[v][i];
		if(to != p)
		{
			sz[v] += sz[to];
			for(int k = 0; k <= allsz + sz[to]; k++)
			{
				dp0[v][k] = 1e18;
				dp1[v][k] = 1e18;
			}
			for(int k = 0; k <= allsz; k++)
			{
				for(int k1 = 0; k1 <= sz[to]; k1++)
				{
					dp0[v][k + k1] = min(dp0[v][k + k1], prev0[k] + min(dp0[to][k1], dp1[to][k1]));
					dp1[v][k + k1] = min(dp1[v][k + k1], prev1[k] + min(dp0[to][k1], dp1[to][k1]));
					dp1[v][k + k1] = min(dp1[v][k + k1], prev0[k] + dp1[to][k1]);
					if(k1 > 0)
					{
						dp1[v][k + k1] = min(dp1[v][k + k1], min(prev1[k], prev0[k]) + dp0[to][k1 - 1] + d[to]);
					}
				}
			}
			allsz += sz[to];
			for(int k = 0; k <= allsz; k++)
			{
				prev1[k] = dp1[v][k];
				prev0[k] = dp0[v][k];
			}
		}
	}
	for(int k = allsz; k >= 0; k--)
	{
		dp1[v][k + 1] = min(1LL * 1e18, dp1[v][k] + d[v]);
	}
	dp1[v][0] = 1e18;
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	d.resize(n + 1);
	sz.resize(n + 1);
	g.resize(n + 1);
	prev0.resize(n + 2);
	prev1.resize(n + 2);
	used.resize(n + 1);
	dp0.resize(n + 1, vector <int> (n + 2, 1e18));
	dp1.resize(n + 1, vector <int> (n + 2, 1e18));
	for(int i = 0; i < n; i++)
	{
		cin >> d[i];
	}
	for(int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(int i = 0; i < n; i++)
	{
		if(!used[i])
		{
			dfs(i);
			g[n].push_back(i);
		}
	}
	dfs(n);
	for(int i = n - 1; i >= 0; i--)
	{
		dp0[n][i] = min(dp0[n][i], dp0[n][i + 1]);
	}
	int q;
	cin >> q;
	while(q--)
	{
		int s;
		cin >> s;
		int l = 0, r= n + 1;
		while(r - l > 1)
		{
			int midd = (r + l) / 2;
			if(dp0[n][midd] <= s)
			{
				l = midd;
			}
			else
			{
				r = midd;
			}
		}
		cout << l << "\n";
	}
  	return 0;
}

Compilation message (stderr)

dzumbus.cpp: In function 'void dfs(long long int, long long int)':
dzumbus.cpp:22:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < g[v].size(); i++)
                  ~~^~~~~~~~~~~~~
dzumbus.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[v].size(); i++)
                 ~~^~~~~~~~~~~~~

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