#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
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);
| ~~~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
2424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
2636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
