This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1010;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, m, q, d[N], sz[N];
vector<int> g[N];
ll dp[N][N][3], ndp[N][N][3], ans[N], nans[N];
bool was[N];
void solve(int x, int fa) {
was[x] = true;
dp[x][0][0] = 0;
dp[x][0][1] = d[x];
sz[x] = 1;
for (int y : g[x]) {
if (y == fa) continue;
solve(y, x);
for (int i = 0; i <= sz[x]; i++)
for (int k = 0; k < 3; k++)
ndp[x][i][k] = dp[x][i][k];
for (int i = 0; i <= sz[x]; i++) {
for (int j = 0; j <= sz[y]; j++) {
dp[x][i + j][0] = min(dp[x][i + j][0], ndp[x][i][0] + dp[y][j][0]);
dp[x][i + j][0] = min(dp[x][i + j][0], ndp[x][i][0] + dp[y][j][1]);
dp[x][i + j][0] = min(dp[x][i + j][0], ndp[x][i][0] + dp[y][j][2]);
dp[x][i + j][1] = min(dp[x][i + j][1], ndp[x][i][1] + dp[y][j][0]);
dp[x][i + j][1] = min(dp[x][i + j][1], ndp[x][i][1] + dp[y][j][1]);
dp[x][i + j][1] = min(dp[x][i + j][1], ndp[x][i][1] + dp[y][j][2]);
dp[x][i + j][2] = min(dp[x][i + j][2], ndp[x][i][2] + dp[y][j][0]);
dp[x][i + j + 1][2] = min(dp[x][i + j + 1][2], ndp[x][i][2] + dp[y][j][1]);
dp[x][i + j][2] = min(dp[x][i + j][2], ndp[x][i][2] + dp[y][j][2]);
dp[x][i + j + 1][2] = min(dp[x][i + j + 1][2], ndp[x][i][1] + dp[y][j][2]);
dp[x][i + j + 2][2] = min(dp[x][i + j + 2][2], ndp[x][i][1] + dp[y][j][1]);
}
}
sz[x] += sz[y];
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &d[i]);
for (int i = 1; i <= m; i++) {
int a, b;
scanf("%d%d", &a, &b);
g[a].push_back(b);
g[b].push_back(a);
}
for (int i = 1; i <= n; i++)
for (int j = 0; j <= n; j++)
for (int k = 0; k < 3; k++)
dp[i][j][k] = inf;
int cur_sz = 0;
for (int i = 0; i < N; i++) ans[i] = inf;
ans[0] = 0;
for (int i = 1; i <= n; i++) if (!was[i]) {
solve(i, i);
for (int j = 0; j < N; j++) nans[j] = inf;
for (int j = 0; j <= cur_sz; j++)
for (int k = 0; k <= sz[i]; k++)
nans[j + k] = min(nans[j + k], ans[j] + min({dp[i][k][0], dp[i][k][1], dp[i][k][2]}));
for (int j = 0; j < N; j++) ans[j] = min(ans[j], nans[j]);
cur_sz += sz[i];
}
vector<pair<ll, int>> f;
for (int i = 0; i < N; i++) f.emplace_back(ans[i], i);
sort(f.begin(), f.end());
for (int i = 1; i < (int) f.size(); i++) f[i].second = max(f[i].second, f[i - 1].second);
scanf("%d", &q);
while (q--) {
int s;
scanf("%d", &s);
int r = 0;
for (auto& p : f) if (p.first <= s) r = max(r, p.second);
printf("%d\n", r);
}
return 0;
}
Compilation message (stderr)
dzumbus.cpp: In function 'int main()':
dzumbus.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
44 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
dzumbus.cpp:45:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | for (int i = 1; i <= n; i++) scanf("%d", &d[i]);
| ~~~~~^~~~~~~~~~~~~
dzumbus.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | scanf("%d%d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~
dzumbus.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
72 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
dzumbus.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
75 | scanf("%d", &s);
| ~~~~~^~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |