// In the name of God
// Hope is last to die
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
// typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb push_back
#define int long long
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define len(x) ((int)(x).size())
const int maxn = 1000 + 100;
const ll inf = 1e15 + 7;
ll n, m, dp[maxn][maxn][2], tmp[maxn][2], cnt[maxn], a[maxn], ans[maxn];
bool mark[maxn];
vector<int> adj[maxn];
void pre_dfs(int v){
mark[v] = 1;
for(auto u: adj[v]){
if(!mark[u]) pre_dfs(u);
}
}
void dfs(int v, int p){
cnt[v] = 1;
for(auto u: adj[v]){
if(u == p) continue;
dfs(u, v);
for(int i = 0; i <= cnt[u] + cnt[v]; i++) tmp[i][0] = tmp[i][1] = inf;
for(int i = 0; i <= cnt[v]; i++){
for(int j = 0; j <= cnt[u]; j++){
if(i == 0){
if(j < 2) continue;
smin(tmp[i + j][0], min(dp[u][j][0], dp[u][j][1]));
}
else if(i == 1) continue;
else{
if(j == 0) smin(tmp[i][0], dp[v][i][0]);
else if(j == 1) continue;
else{
smin(tmp[i + j][0], dp[v][i][0] + min(dp[u][j][0], dp[u][j][1]));
}
}
}
}
for(int i = 0; i <= cnt[v]; i++){
for(int j = 0; j <= cnt[u]; j++){
if(i == 0) continue;
else if(i == 1){
if(j == 0) continue;
else if(j == 1) smin(tmp[i + j][1], a[v] + a[u]);
else{
smin(tmp[i + j][1], a[v] + dp[u][j][1]);
}
}
else{
if(j == 0) smin(tmp[i][1], dp[v][i][1]);
if(j == 1) smin(tmp[i + j][1], dp[v][i][1] + a[u]);
else{
smin(tmp[i + j][1], dp[v][i][1] + min(dp[u][j][1], dp[u][j][0]));
}
}
}
for(int j = 3; j <= cnt[u]; j++){
if(i == 0) continue;
if(i == 1) smin(tmp[i + j][1], a[v] + a[u] + dp[u][j - 1][0]);
smin(tmp[i + j][1], dp[v][i][1] + a[u] + dp[u][j - 1][0]);
}
}
cnt[v] += cnt[u];
for(int i = 0; i <= cnt[v]; i++){
dp[v][i][0] = tmp[i][0];
dp[v][i][1] = tmp[i][1];
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 0; i <= n + 10; i++) for(int j = 0; j <= n + 10; j++) dp[i][j][0] = dp[i][j][1] = inf;
for(int i = 1; i <= n; i++) cin >> a[i];
a[n + 1] = inf;
for(int i = 0; i < m; i++){
int u, v; cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
}
for(int i = 1; i <= n; i++) if(!mark[i]){
pre_dfs(i);
adj[n + 1].pb(i);
}
dfs(n + 1, -1);
int q; cin >> q;
vector<pll> vec;
for(int i = 0; i < q; i++){
int x; cin >> x;
vec.pb(mp(x, i));
}
sort(all(vec));
reverse(all(vec));
int cur = n;
for(int i = 0; i < q; i++){
while(cur >= 2 && dp[n + 1][cur][0] > vec[i].F) cur--;
if(cur != 1) ans[vec[i].S] = cur;
}
for(int i = 0; i < q; i++){
if(ans[i] < 0) while(true){};
cout << ans[i] << '\n';
}
// dfs(1, -1);
// cout << dp[1][4][1] << '\n';
// for(int i = 1; i <= n; i++){
// for(int j = 0; j <= n; j++){
// cout << i << ' ' << j << ' ' << dp[i][j][0] << ' ' << dp[i][j][1] << '\n';
// }
// }
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
18012 KB |
Output is correct |
| 2 |
Correct |
11 ms |
18104 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
18012 KB |
Output is correct |
| 2 |
Correct |
11 ms |
18104 KB |
Output is correct |
| 3 |
Incorrect |
39 ms |
23484 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
7356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
18012 KB |
Output is correct |
| 2 |
Correct |
11 ms |
18104 KB |
Output is correct |
| 3 |
Incorrect |
39 ms |
23484 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
