#include "bits/stdc++.h"
#define endl '\n'
#define int long long
const int maxn = 1005;
const int inf = 1e13;
const int mod = 1e9 + 7;
using namespace std;
using lint = long long;
using pii = pair<int,int>;
int n, m, q;
int s[maxn];
vector<int> adj[maxn];
int sz[maxn];
int dp[maxn][maxn][3];
int now[maxn][3], prv[maxn][3];
int p[maxn];
int tmp[maxn], ans[maxn];
void dfs(int u) {
sz[u] = 1;
for(int v : adj[u]) {
if(v == p[u])
continue;
p[v] = u;
dfs(v);
sz[u] += sz[v];
}
for(int k = 0; k <= sz[u]; k++)
now[k][0] = now[k][1] = now[k][2] = inf;
now[0][0] = 0;
now[0][1] = s[u];
now[0][2] = inf;
for(int v : adj[u]) {
if(v == p[u])
continue;
for(int k = 0; k <= sz[u]; k++) {
prv[k][0] = now[k][0];
prv[k][1] = now[k][1];
prv[k][2] = now[k][2];
now[k][0] = now[k][1] = now[k][2] = inf;
}
for(int k = 0; k <= sz[u]; k++)
for(int x = 0; x <= min(sz[v], k); x++) {
int r0 = min({dp[v][x][0], dp[v][x][1], dp[v][x][2]}) + prv[k - x][0];
int r1 = dp[v][x][0] + prv[k - x][1];
int r2 = min({
k - x >= 2 ? dp[v][x][1] + prv[k - x - 2][1] : inf,
k - x >= 1 ? dp[v][x][1] + prv[k - x - 1][2] : inf,
dp[v][x][0] + prv[k - x][2],
dp[v][x][2] + prv[k - x][2]
});
now[k][0] = min(now[k][0], r0);
now[k][1] = min(now[k][1], r1);
now[k][2] = min(now[k][2], r2);
}
}
for(int k = 0; k <= sz[u]; k++) {
dp[u][k][0] = now[k][0];
dp[u][k][1] = now[k][1];
dp[u][k][2] = now[k][2];
}
}
void precomp() {
for(int k = 1; k <= n; k++)
ans[k] = inf;
ans[0] = 0;
for(int v = 1; v <= n; v++) {
if(p[v])
continue;
dfs(v);
for(int k = 0; k <= n; k++) {
tmp[k] = ans[k];
ans[k] = inf;
}
for(int k = 0; k <= n; k++)
for(int x = 0; x <= min(sz[v], k); x++) {
int res = min({dp[v][x][0], dp[v][x][1], dp[v][x][2]}) + tmp[k - x];
ans[k] = min(ans[k], res);
}
}
}
int solve(int x) {
if(n < 2)
return 0;
int l = 2, r = n, mid;
while(l < r - 1) {
mid = (l + r) / 2;
if(ans[mid] > x)
r = mid - 1;
else
l = mid;
}
return ans[r] > x ? (ans[l] > x ? 0 : l) : r;
}
signed main() {
#ifdef Local
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> s[i];
for(int i = 0, x, y; i < m; i++) {
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
precomp();
cin >> q;
while(q--) {
int x;
cin >> x;
cout << solve(x) << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
250 ms |
10904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
250 ms |
10904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
2692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
250 ms |
10904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
