#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e14;
const int MAXN = 1e3 + 25;
int n, m;
vector <int> adj[MAXN];
ll d[MAXN], sze[MAXN];
bool vis[MAXN];
void pre (int pos, int par) {
vis[pos] = 1; sze[pos] = 1;
for (int j = 0; j < (int)adj[pos].size(); j++) {
if (adj[pos][j] == par) {
adj[pos].erase(adj[pos].begin() + j);
}
}
for (auto j : adj[pos]) {
pre(j, pos); sze[pos] += sze[j];
}
}
ll dp[MAXN][MAXN][2][2];
ll ans (int pos, int m, int a, int b) {
ll &ret = dp[pos][m][a][b];
if (ret != -1) return ret;
if (m > sze[pos]) return ret = inf;
ret = 0;
if (!b) {
vector <vector <ll>> dp2(2, vector <ll> (m + 1));
for (int i = 1; i <= m; i++) dp2[0][i] = inf;
int c = 0;
for (auto j : adj[pos]) {
c ^= 1;
for (int i = 0; i <= m; i++) dp2[c][i] = inf;
for (int i = 0; i <= m; i++) {
for (int l = i; l <= m; l++) {
dp2[c][l] = min(dp2[c][l], dp2[c ^ 1][l - i] + min(ans(j, i, 0, 1), ans(j, i, 0, 0)));
}
}
}
return ret = dp2[c][m];
}
if (!a && b) {
vector <vector <vector <ll>>> dp2(2, vector <vector <ll>> (2, vector <ll> (m + 1)));
for (int i = 1; i <= m; i++) dp2[0][0][i] = dp2[0][1][i] = inf;
dp2[0][1][0] = inf;
int c = 0;
for (auto j : adj[pos]) {
c ^= 1;
for (int i = 0; i <= m; i++) dp2[c][0][i] = dp2[c][1][i] = inf;
for (int i = 0; i <= m; i++) {
for (int l = i; l <= m; l++) {
dp2[c][0][l] = min(dp2[c][0][l], dp2[c ^ 1][0][l - i] + ans(j, i, 1, 0));
dp2[c][1][l] = min(dp2[c][1][l], min(dp2[c ^ 1][0][l - i] + ans(j, i, 1, 1), dp2[c ^ 1][1][l - i] + min(ans(j, i, 1, 1), ans(j, i, 1, 0))));
}
}
}
return ret = d[pos] + min(dp2[c][0][m], dp2[c][1][m - 1]);
}
if (a && b) {
vector <vector <ll>> dp2(2, vector <ll> (m + 1));
for (int i = 1; i <= m; i++) dp2[0][i] = inf;
int c = 0;
for (auto j : adj[pos]) {
c ^= 1;
for (int i = 0; i <= m; i++) dp2[c][i] = inf;
for (int i = 0; i <= m; i++) {
for (int l = i; l <= m; l++) {
dp2[c][l] = min(dp2[c][l], dp2[c ^ 1][l - i] + min(ans(j, i, 1, 1), ans(j, i, 1, 0)));
}
}
}
return ret = d[pos] + dp2[c][m - 1];
}
}
int main () {
memset(dp, -1, sizeof(dp));
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> d[i];
for (int i = 1; i <= m; i++) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
adj[0].push_back(i); pre(i, -1); sze[0] += sze[i];
}
}
d[0] = inf; sze[0]++;
int q; cin >> q;
while (q--) {
ll x; cin >> x;
ll ret = 0;
for (int i = 1; i <= n; i++) {
if (ans(0, i, 0, 0) <= x) ret = i;
//cout << ans(0, i, 0, 0) << " ";
}
cout << ret << '\n';
}
}
Compilation message
dzumbus.cpp: In function 'll ans(int, int, int, int)':
dzumbus.cpp:74:1: warning: control reaches end of non-void function [-Wreturn-type]
74 | }
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1033 ms |
34180 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1033 ms |
34180 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
210 ms |
35524 KB |
Output is correct |
| 2 |
Correct |
155 ms |
35172 KB |
Output is correct |
| 3 |
Correct |
186 ms |
35724 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1033 ms |
34180 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
