oj.uz

Submission #444669

# Submission time Handle Problem Language Result Execution time Memory
444669 2021-07-14T16:22:48 Z penguinhacker Džumbus (COCI19_dzumbus) C++14
110 / 110
 275 ms 8104 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

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

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

void mrg(int u, int v) {
	vector<ar<ll, 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 (i+1<dp[u].size())
				smin(r[i+j+1][1], dp[u][i][0]+dp[v][j][1]+a[u]);
			if (j+1<dp[v].size())
				smin(r[i+j+1][1], 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], dp[u][i][0]+dp[v][j][0]+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

dzumbus.cpp: In function 'void mrg(int, int)':
dzumbus.cpp:22:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for (int i=0; i<dp[u].size(); ++i)
      |                ~^~~~~~~~~~~~~
dzumbus.cpp:23:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   for (int j=0; j<dp[v].size(); ++j) {
      |                 ~^~~~~~~~~~~~~
dzumbus.cpp:26:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |    if (i+1<dp[u].size())
      |        ~~~^~~~~~~~~~~~~
dzumbus.cpp:28:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    if (j+1<dp[v].size())
      |        ~~~^~~~~~~~~~~~~
dzumbus.cpp:30:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    if (i+1<dp[u].size()&&j+1<dp[v].size())
      |        ~~~^~~~~~~~~~~~~
dzumbus.cpp:30:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |    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:62:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |  assert(dp[0].size()==n+2);
      |         ~~~~~~~~~~~~^~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4812 KB Output is correct
2 Correct 11 ms 5632 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4812 KB Output is correct
2 Correct 11 ms 5632 KB Output is correct
3 Correct 266 ms 8104 KB Output is correct
4 Correct 269 ms 7468 KB Output is correct
5 Correct 275 ms 6888 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 1076 KB Output is correct
2 Correct 62 ms 2236 KB Output is correct
3 Correct 68 ms 2616 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4812 KB Output is correct
2 Correct 11 ms 5632 KB Output is correct
3 Correct 266 ms 8104 KB Output is correct
4 Correct 269 ms 7468 KB Output is correct
5 Correct 275 ms 6888 KB Output is correct
6 Correct 63 ms 1076 KB Output is correct
7 Correct 62 ms 2236 KB Output is correct
8 Correct 68 ms 2616 KB Output is correct
9 Correct 269 ms 2760 KB Output is correct
10 Correct 266 ms 3248 KB Output is correct
11 Correct 269 ms 2976 KB Output is correct