#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
ll min(const ll &a, const ll &b){
return (a < b) ? a : b;
}
ll max(const ll &a, const ll &b){
return (a > b) ? a : b;
}
const ll Mod = 1000000007;
const int maxN = 5e3 + 1;
const ll inf = 1e18;
int n, m;
bool visited[maxN];
vector <ll> dp[maxN][3];
int a[maxN];
vector <int> adj[maxN];
void predfs(int u){
visited[u] = 1;
for (const int &v: adj[u]){
if (!visited[v]){
predfs(v);
}
}
}
void dfs(int u, int p){
dp[u][0] = {0, inf};
dp[u][1] = {a[u], inf};
dp[u][2] = {inf, inf};
for (const int &t: adj[u]){
if (t != p){
dfs(t, u);
int s = dp[u][0].size() + dp[t][0].size() - 1;
vector <ll> tem0(s, inf);
vector <ll> tem1(s, inf);
vector <ll> tem2(s, inf);
for (int i = 0; i < dp[u][0].size(); ++i){
for (int j = 0; j < dp[t][0].size(); ++j){
tem0[i + j] = min(tem0[i + j], dp[u][0][i] + min(dp[t][0][j], min(dp[t][1][j], dp[t][2][j])));
tem1[i + j] = min(tem1[i + j], dp[u][1][i] + dp[t][0][j]);
tem2[i + j] = min(tem2[i + j], dp[u][2][i] + min(dp[t][2][j], dp[t][0][j]));
if (i + j + 1 < tem2.size())
tem2[i + j + 1] = min(tem2[i + j + 1], min(dp[u][2][i] + dp[t][1][j], dp[u][1][i] + dp[t][2][j]));
if (i + j + 2 < tem2.size())
tem2[i + j + 2] = min(tem2[i + j + 2], dp[u][1][i] + dp[t][1][j]);
}
}
dp[u][0] = tem0;
dp[u][1] = tem1;
dp[u][2] = tem2;
}
}
}
void Init(){
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= m; ++i){
int u, v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
a[0] = INT_MAX;
for (int i = 1; i <= n; ++i){
if (!visited[i]){
predfs(i);
adj[0].pb(i);
}
}
dfs(0, -1);
int q; cin >> q; while (q--){
int s; cin >> s;
int t = upper_bound(dp[0][0].begin() + 2, dp[0][0].end(), s) - dp[0][0].begin() - 1;
if (t == 1) --t;
cout << t << "\n";
}
}
int main(){
if (fopen(taskname".txt", "r")){
freopen(taskname".txt", "r", stdin);
}
faster
//freopen(taskname.inp, "r", stdin)
//freopen(taskname.out, "w", stdout)
Init();
}
Compilation message
dzumbus.cpp: In function 'void dfs(int, int)':
dzumbus.cpp:50:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int i = 0; i < dp[u][0].size(); ++i){
| ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:51:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for (int j = 0; j < dp[t][0].size(); ++j){
| ~~^~~~~~~~~~~~~~~~~
dzumbus.cpp:55:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | if (i + j + 1 < tem2.size())
| ~~~~~~~~~~^~~~~~~~~~~~~
dzumbus.cpp:57:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | if (i + j + 2 < tem2.size())
| ~~~~~~~~~~^~~~~~~~~~~~~
dzumbus.cpp: In function 'int main()':
dzumbus.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | freopen(taskname".txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7892 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
9940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7892 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
9940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
2892 KB |
Output is correct |
| 2 |
Incorrect |
34 ms |
2660 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
7892 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
9940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
