#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
#define pb push_back
#define sz(x) int32_t(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
const int N = 1001;
const ll inf = 1e18+1;
ll d[N];
vector<ll> dp[N][3];
int n, m;
vector<int> adj[N];
vector<ll> comb(vector<ll> a, vector<ll> b) {
vector<ll> ret(sz(a) + sz(b) - 1, inf);
for (int i = 0; i < sz(a); i++) {
for (int j = 0; j < sz(b); j++) {
ret[i+j] = min(ret[i+j], a[i] + b[j]);
}
}
return ret;
}
vector<ll> minz(vector<ll> a, vector<ll> b) {
vector<ll> ret(max(sz(a), sz(b)));
for (int i = 0; i < sz(ret); i++) {
ret[i] = min((i < sz(a) ? a[i] : inf), (i < sz(b) ? b[i] : inf));
}
return ret;
}
vector<ll> add(vector<ll> a, ll val) {
vector<ll> ret = a;
for (auto &i : ret)i = min(inf, i+val);
return ret;
}
vector<ll> shift(vector<ll> a, int x) {
vector<ll> ret = a;
while (x--)ret.insert(ret.begin(), inf);
return ret;
}
//N,Y W,N Y,Y
void dfs(int u, int p) {
dp[u][0] = dp[u][1] = {0};
dp[u][2] = {inf, d[u]};
vector<ll> x = {0}, y = {};
bool f = false;
for (auto &v : adj[u]) {
if (v == p)continue;
dfs(v, u);
vector<ll> c = dp[u][0], c2 = dp[u][1], c3 = dp[u][2];
dp[u][1] = minz(comb(c2, dp[v][1]), comb(c2, dp[v][0]));
dp[u][2] = minz(comb(c3, dp[v][2]), comb(c3, dp[v][1]));
dp[u][0] = minz(comb(x, add(shift(dp[v][2], 1), d[u])), minz(comb(c, dp[v][1]), comb(y, dp[v][2])));
if (!f)y = add(shift(dp[v][2], 1), d[u]);
else y = minz(comb(x, add(shift(dp[v][2], 1), d[u])), comb(y, dp[v][1]));
x = comb(x, dp[v][1]);
f = true;
}
}
bool vis[N];
void dfs2(int u) {
vis[u] = true;
for (auto &v : adj[u]) {
if (!vis[v]) {
dfs2(v);
}
}
}
signed main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
d[0] = inf;
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].pb(v);
adj[v].pb(u);
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
adj[0].pb(i);
dfs2(i);
}
}
dfs(0, 0);
int q;
cin >> q;
while (q--) {
ll x;
cin >> x;
int l = 1, r = n, ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (min((sz(dp[0][0]) > mid ? dp[0][0][mid] : inf), (sz(dp[0][1]) > mid ? dp[0][1][mid] : inf)) <= x) {
ans = mid;
l = mid+1;
} else {
r = mid-1;
}
}
cout << ans << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
2652 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
