// ~~ icebear love attttt ~~
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
template<class T>
bool minimize(T &a, const T &b) {
if (a > b) return a = b, true;
return false;
}
template<class T>
bool maximize(T &a, const T &b) {
if (a < b) return a = b, true;
return false;
}
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "gen"
#define prev love
const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 1000 + 5;
int n, m, q;
ll dp[N][N][3], f[N][3], need[N];
int sz[N], ans[200005];
vector<int> G[N];
ii Q[200005];
void dfs(int u, int par) {
if (sz[u]) return;
sz[u] = 1;
dp[u][0][0] = 0;
dp[u][1][1] = need[u];
for(int v : G[u]) if (v != par) {
dfs(v, u);
FOR(j, 0, sz[u]) REP(k, 3) {
f[j][k] = dp[u][j][k];
dp[u][j][k] = INF;
}
FOR(j, 0, sz[u]) REP(x, 3)
FOR(k, 0, sz[v]) REP(y, 3) {
if (x == 0 && y == 1) continue; // choose only v -> unsatisfied
int state = x;
if (x > 0 && y > 0) state = 2; // choose u and child
minimize(dp[u][j + k][state], f[j][x] + dp[v][k][y]);
}
sz[u] += sz[v];
}
}
void init(void) {
cin >> n >> m;
FOR(i, 1, n) cin >> need[i];
FOR(i, 1, m) {
int u, v;
cin >> u >> v;
G[u].pb(v);
G[v].pb(u);
}
cin >> q;
FOR(i, 1, q) cin >> Q[i].fi, Q[i].se = i;
sort(Q + 1, Q + q + 1);
}
void process(void) {
FOR(i, 0, n) FOR(j, 0, n + 1) REP(k, 3) dp[i][j][k] = INF;
FOR(i, 1, n) if (sz[i] == 0) {
dfs(i, -1);
G[0].pb(i);
}
need[0] = INF;
dfs(0, -1);
vector<pair<ll, int>> best;
FOR(j, 2, n) best.pb(mp(dp[0][j][0], j));
sort(all(best));
int res = 0, j = 0;
FOR(i, 1, q) {
while(j < n - 1 && best[j].fi <= Q[i].fi) {
maximize(res, best[j].se);
j++;
}
ans[Q[i].se] = res;
}
FOR(i, 1, q) cout << ans[i] << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int tc = 1;
// cin >> tc;
while(tc--) {
init();
process();
}
return 0;
}
Compilation message (stderr)
dzumbus.cpp: In function 'int main()':
dzumbus.cpp:111:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
111 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |