oj.uz

Submission #251552

# Submission time Handle Problem Language Result Execution time Memory
251552 2020-07-21T19:16:45 Z MrRobot_28 Džumbus (COCI19_dzumbus) C++17
110 / 110
 82 ms 18936 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16256 KB Output is correct
2 Correct 19 ms 16384 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16256 KB Output is correct
2 Correct 19 ms 16384 KB Output is correct
3 Correct 69 ms 17232 KB Output is correct
4 Correct 65 ms 17272 KB Output is correct
5 Correct 65 ms 16820 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1272 KB Output is correct
2 Correct 43 ms 1144 KB Output is correct
3 Correct 46 ms 888 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16256 KB Output is correct
2 Correct 19 ms 16384 KB Output is correct
3 Correct 69 ms 17232 KB Output is correct
4 Correct 65 ms 17272 KB Output is correct
5 Correct 65 ms 16820 KB Output is correct
6 Correct 46 ms 1272 KB Output is correct
7 Correct 43 ms 1144 KB Output is correct
8 Correct 46 ms 888 KB Output is correct
9 Correct 64 ms 18296 KB Output is correct
10 Correct 82 ms 18936 KB Output is correct
11 Correct 65 ms 18704 KB Output is correct