#include <bits/stdc++.h>
using namespace std;
using ll = long long;
inline void remin(ll& x, ll y) { x = (y < x ? y : x); }
const int N = (int)1e3 + 1, Q = (int)2e5;
int n, m, q, d[N];
bool vis[N];
vector<ll> dp[N][2];
vector<int> adj[N];
void dfs(int x, int pr) {
vis[x] = true;
for(auto& e : adj[x]) {
if(e != pr) {
dfs(e, x);
}
}
}
void dfs2(int x, int pr) {
dp[x][0] = {0, LLONG_MAX};
dp[x][1] = {LLONG_MAX, LLONG_MAX};
for(auto& e : adj[x]) {
if(e != pr) {
dfs2(e, x);
vector<ll> res((int)dp[x][0].size() + (int)dp[e][0].size() - 1, LLONG_MAX);
for(int i = 0;i < (int)dp[x][0].size();i ++) {
for(int j = 0;j < (int)dp[e][0].size();j ++) {
if(dp[x][1][i] != LLONG_MAX) {
if(dp[e][1][j] != LLONG_MAX)
remin(res[i + j], dp[x][1][i] + dp[e][1][j]);
if(dp[e][0][j] != LLONG_MAX) {
remin(res[i + j + 1], dp[x][1][i] + dp[e][0][j] + d[e]);
remin(res[i + j], dp[x][1][i] + dp[e][0][j]);
}
}
if(dp[x][0][i] != LLONG_MAX) {
if(dp[e][0][j] != LLONG_MAX)
remin(res[i + j + 2], dp[x][0][i] + dp[e][0][j] + d[x] + d[e]);
if(dp[e][1][j] != LLONG_MAX)
remin(res[i + j + 1], dp[x][0][i] + dp[e][1][j] + d[x]);
}
}
}
dp[x][1] = res;
res = vector<ll>((int)dp[x][0].size() + (int)dp[e][0].size() - 1, LLONG_MAX);
for(int i = 0;i < (int)dp[x][0].size();i ++) {
for(int j = 0;j < (int)dp[e][0].size();j ++) {
if(dp[x][0][i] != LLONG_MAX) {
if(dp[e][0][j] != LLONG_MAX)
remin(res[i + j], dp[x][0][i] + dp[e][0][j]);
if(dp[e][1][j] != LLONG_MAX)
remin(res[i + j], dp[x][0][i] + dp[e][1][j]);
}
}
}
dp[x][0] = res;
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
d[0] = 0;
for(int i = 1;i <= n;i ++) {
cin >> d[i];
}
for(int i = 0;i < m;i ++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
for(int i = 1;i <= n;i ++) {
if(!vis[i]) {
dfs(i, -1);
adj[0].push_back(i);
adj[i].push_back(0);
}
}
dfs2(0, -1);
cin >> q;
while(q --) {
int s;
cin >> s;
int lx = 0, rx = n;
while(lx < rx) {
int g = lx + (rx - lx + 1) / 2;
if(dp[0][0][g] <= s) {
lx = g;
} else {
rx = g - 1;
}
}
cout << lx << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
2500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
4940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
