#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 30013;
const ll LOGN = 21;
const ll MAXN = 1100;
//#define int long long
vector<vector<int>> graph;
vector<int> D, dp[MAXN][3];
vector<int> add(const vector<int> &A, const vector<int> &B) {
vector<int> res(A.size() + B.size() - 1, 1e12);
for (int i = 0; i < A.size(); i++) {
for (int j = 0; j < B.size(); j++)
res[i+j] = min(res[i+j], A[i] + B[j]);
}
return res;
}
vector<int> minimize(vector<int> A, const vector<int> &B) {
while (A.size() < B.size())
A.push_back(1e12);
for (int i = 0; i < B.size(); i++)
A[i] = min(A[i], B[i]);
return A;
}
int vis[MAXN];
void dfs(int node, int parent) {
vis[node] = 1;
dp[node][0] = {0};
dp[node][1] = {(ll)1e12, D[node]};
for (auto u : graph[node]) {
if (u == parent)
continue;
dfs(u, node);
dp[node][0] = add(dp[node][0], minimize(dp[u][0], dp[u][2]));
dp[node][1] = add(dp[node][1], dp[u][0]);
dp[node][2] = minimize(add(dp[node][1], minimize(dp[u][1], dp[u][2])),
add(dp[node][2], minimize(dp[u][1], minimize(dp[u][2], dp[u][0]))));
}
}
signed main() {
fast
int N, M, a, b;
cin >> N >> M;
graph = vector<vector<int>>(N+1, vector<int>());
D = vector<int>(N+1);
for (int i = 1; i <= N; i++)
cin >> D[i];
for (int i = 0; i < M; i++) {
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
vector<int> res = {0};
for (int i = 1; i <= N; i++) {
if (!vis[i]) {
dfs(i, i);
res = add(res, minimize(dp[i][0], dp[i][2]));
}
}
for (int i = (int)res.size() - 2; i >= 0; i--)
res[i] = min(res[i+1], res[i]);
int Q, q, val;
cin >> Q;
while (Q--) {
cin >> val;
q = (upper_bound(res.begin(), res.end(), val) - res.begin()) - 1;
cout << q << "\n";
}
}
Compilation message
dzumbus.cpp: In function 'std::vector<int> add(const std::vector<int>&, const std::vector<int>&)':
dzumbus.cpp:17:43: warning: overflow in conversion from 'double' to 'std::vector<int>::value_type' {aka 'int'} changes value from '1.0e+12' to '2147483647' [-Woverflow]
17 | vector<int> res(A.size() + B.size() - 1, 1e12);
| ^~~~
dzumbus.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | for (int i = 0; i < A.size(); i++) {
| ~~^~~~~~~~~~
dzumbus.cpp:19:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for (int j = 0; j < B.size(); j++)
| ~~^~~~~~~~~~
dzumbus.cpp: In function 'std::vector<int> minimize(std::vector<int>, const std::vector<int>&)':
dzumbus.cpp:27:15: warning: overflow in conversion from 'double' to 'std::vector<int>::value_type' {aka 'int'} changes value from '1.0e+12' to '2147483647' [-Woverflow]
27 | A.push_back(1e12);
| ^~~~
dzumbus.cpp:28:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for (int i = 0; i < B.size(); i++)
| ~~^~~~~~~~~~
dzumbus.cpp: In function 'void dfs(int, int)':
dzumbus.cpp:37:34: error: narrowing conversion of '1000000000000' from 'll' {aka 'long long int'} to 'int' [-Wnarrowing]
37 | dp[node][1] = {(ll)1e12, D[node]};
| ^
