#include "bits/stdc++.h"
#define endl '\n'
#define fi first
#define se second
#define int long long
using namespace std;
using lint = int;
using pii = pair<int, int>;
constexpr int maxn = 1005;
constexpr int inf = 1e13;
constexpr int mod = 1e9 + 7;
int n, m, q;
vector<int> adj[maxn];
int d[maxn];
int dp[maxn][maxn][3];
int sz[maxn];
int now[maxn][3], prv[maxn][3];
int tin[maxn];
int timer;
int ans[maxn];
vector<pii> v;
void dfs(int u) {
for(int v : adj[u])
if(tin[v] > tin[u])
dfs(v);
for(int k = 1; k <= sz[u]; k++)
for(int j = 0; j <= 2; j++)
now[k][j] = inf;
now[0][0] = 0;
now[0][1] = d[u];
now[0][2] = inf;
int psz = 1;
for(int v : adj[u]) {
if(tin[v] < tin[u])
continue;
for(int k = 0; k <= sz[u]; k++)
for(int j = 0; j <= 2; j++) {
prv[k][j] = now[k][j];
now[k][j] = inf;
}
for(int a = 0; a <= sz[v]; a++)
for(int b = 0; b <= psz; b++) {
int r0 = min({dp[v][a][0], dp[v][a][1], dp[v][a][2]}) + prv[b][0];
int r1 = dp[v][a][0] + prv[b][1];
int r2 = min({
dp[v][a][0] + prv[b][2],
dp[v][a][2] + prv[b][2],
a >= 1 ? dp[v][a - 1][1] + prv[b][2] : inf,
b >= 1 ? dp[v][a][2] + prv[b - 1][1] : inf,
a >= 1 && b >= 1 ? dp[v][a - 1][1] + prv[b - 1][1] : inf
});
now[a + b][0] = min(now[a + b][0], r0);
now[a + b][1] = min(now[a + b][1], r1);
now[a + b][2] = min(now[a + b][2], r2);
}
psz += sz[v];
}
for(int k = 0; k <= sz[u]; k++)
for(int j = 0; j <= 2; j++)
dp[u][k][j] = now[k][j];
}
void dfs2(int u) {
tin[u] = ++timer;
sz[u] = 1;
for(int v : adj[u])
if(!tin[v]) {
dfs2(v);
sz[u] += sz[v];
}
}
void precomp() {
d[0] = inf;
sz[0] = 1;
for(int i = 1; i <= n; i++)
if(!tin[i]) {
dfs2(i);
adj[0].push_back(i);
sz[0] += sz[i];
}
dfs(0);
}
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 >> d[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;
for(int i = 1, x; i <= q; i++) {
cin >> x;
v.push_back({x, i});
}
sort(v.begin(), v.end());
for(int k = n; k >= 0; k--)
while(!v.empty() && v.back().fi >= dp[0][k][0]) {
ans[v.back().se] = k;
v.pop_back();
}
for(int i = 1; i <= q; i++)
cout << ans[i] << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
10956 KB |
Output is correct |
| 2 |
Correct |
12 ms |
12152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
10956 KB |
Output is correct |
| 2 |
Correct |
12 ms |
12152 KB |
Output is correct |
| 3 |
Incorrect |
63 ms |
19120 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
6060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
10956 KB |
Output is correct |
| 2 |
Correct |
12 ms |
12152 KB |
Output is correct |
| 3 |
Incorrect |
63 ms |
19120 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
