#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1005;
vector<int> adj[N], tempadj[N];
bool vis[N];
void build(int i, int par) {
vis[i] = 1;
vector<int> newadj;
for (auto nxt : tempadj[i]) {
if (nxt == par) continue;
build(nxt, i);
newadj.push_back(nxt);
}
tempadj[i] = newadj;
}
int sz[N], tempsz[N], st[N], t;
void build2(int i) {
st[i] = t++;
tempsz[i] = 1;
for (auto nxt : tempadj[i]) {
build2(nxt);
tempsz[i] += tempsz[nxt];
}
}
ll a[N], dp[N][N][2][2];
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int n, m;
cin >> n >> m;
ll tempa[n + 1];
for (int i = 1; i <= n; i++) {
cin >> tempa[i];
}
for (int i = 0, u, v; i < m; i++) {
cin >> u >> v;
tempadj[u].push_back(v);
tempadj[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
if (vis[i]) continue;
build(i, 0);
tempadj[0].push_back(i);
}
tempa[0] = 1e18;
build2(0);
for (int i = 0; i <= n; i++) {
adj[st[i]] = tempadj[i];
for (auto &nxt : adj[st[i]]) nxt = st[nxt];
}
for (int i = 0; i <= n; i++) {
a[st[i]] = tempa[i];
sz[st[i]] = tempsz[i];
}
for (int i = n; i >= 0; i--) {
for (int f = 0; f < 2; f++) {
m = adj[i].size();
ll dp2[m + 1][sz[i] + 1][3]{};
for (int l = 0; l <= sz[i]; l++) dp2[m][l][0] = dp2[m][l][1] = 1e18;
dp2[m][0][0] = 0;
ll s = 0;
for (int k = m - 1; k >= 0; k--) {
s += sz[adj[i][k]];
for (int l = 0; l <= s; l++) {
for (int f2 = 0; f2 < 2; f2++) {
dp2[k][l][f2] = 1e18;
for (int o = 0; o <= sz[adj[i][k]]; o++) {
dp2[k][l][f2] = min(dp2[k][l][f2], dp2[k + 1][l - o][f2] + dp[adj[i][k]][o][0][f]);
dp2[k][l][f2] = min(dp2[k][l][f2], dp2[k + 1][l - o][0] + dp[adj[i][k]][o][1][f]);
}
}
}
for (int l = s + 1; l <= sz[i]; l++) {
for (int f2 = 0; f2 < 2; f2++) {
dp2[k][l][f2] = 1e18;
}
}
}
for (int j = 0; j <= sz[i]; j++) {
for (int par = 0; par < 2; par++) {
dp[i][j][f][par] = 1e18;
if (f) {
if (j == 0) continue;
if (par) {
dp[i][j][f][par] = min(dp[i][j][f][par], dp2[0][j - 1][0] + a[i]);
} else {
dp[i][j][f][par] = min(dp[i][j][f][par], dp2[0][j - 1][1] + a[i]);
}
} else {
dp[i][j][f][par] = dp2[0][j][0];
}
}
}
for (int j = sz[i] + 1; j <= n; j++) {
for (int par = 0; par < 2; par++) {
dp[i][j][f][par] = 1e18;
}
}
}
}
int q;
cin >> q;
while (q--) {
ll s;
cin >> s;
for (int i = n; i >= 0; i--) {
if (dp[0][i][0][0] <= s) {
cout << i << '\n';
break;
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
855 ms |
31980 KB |
Output is correct |
| 2 |
Execution timed out |
1029 ms |
23788 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
855 ms |
31980 KB |
Output is correct |
| 2 |
Execution timed out |
1029 ms |
23788 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
6236 KB |
Output is correct |
| 2 |
Correct |
30 ms |
5972 KB |
Output is correct |
| 3 |
Correct |
41 ms |
6644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
855 ms |
31980 KB |
Output is correct |
| 2 |
Execution timed out |
1029 ms |
23788 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
