Submission #233787

#TimeUsernameProblemLanguageResultExecution timeMemory
233787jungsnowDžumbus (COCI19_dzumbus)C++14
110 / 110
808 ms19320 KiB
#include <bits/stdc++.h> using namespace std; #define TRACE(x) cerr << #x << " = " << x << endl #define _ << " _ " << typedef long long ll; typedef long double ld; const int N = 1010, MAXQ = 2e5 + 10; const ll INF = 1e15; const int dummy = 0; int n, m, q; ll dp[N][N][2], D[N]; int numChild[N] ; bool vis[N]; vector<int> adj[N]; void con(int par, int i) { vis[i] = 1; for (int v : adj[i]) if (v != par) { if (!vis[v]) { vis[v] = 1; con(i, v); } } } void dfs(int par, int u) { numChild[u] = 1; dp[u][0][0] = 0; for (int v : adj[u]) if (v != par) { dfs(u, v); numChild[u] += numChild[v]; for (int i = numChild[u]; i >= 2; i--) { for (int j = min(i, numChild[v]); j >= 0; j--) { ///use current node; dp[u][i][1] = min(dp[u][i][1], dp[u][i - j][1] + min(dp[v][j][0], dp[v][j][1])); if (i - j - 1 >= 0 && j - 1 >= 0) { dp[u][i][1] = min(dp[u][i][1], dp[u][i - j - 1][0] + D[u] + dp[v][j - 1][0] + D[v]); } if (i - j - 1 >= 0) { dp[u][i][1] = min(dp[u][i][1], dp[u][i - j - 1][0] + D[u] + dp[v][j][1]); } if (j - 1 >= 0) { dp[u][i][1] = min(dp[u][i][1], dp[u][i - j][1] + dp[v][j - 1][0] + D[v]); } ///not use current node dp[u][i][0] = min(dp[u][i][0], dp[u][i - j][0] + min(dp[v][j][0], dp[v][j][1])); } } } } int main() { //freopen("dzumbus.inp", "r", stdin); //freopen("dzumbus.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) cin >> D[i]; D[0] = INF; for (int u, v, i = 1; i <= m; i++) { cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } for (int i = 1; i <= n; i++) { if (!vis[i]) { vis[i] = 1; con(dummy, i); adj[dummy].push_back(i); } } for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { dp[i][j][0] = dp[i][j][1] = INF; } } dfs(-1, 0); cin >> q; while (q--) { ll S; cin >> S; for (int i = n ; i >= 0; i--) { if (dp[0][i][0] <= S) { //cout << dp[0][i][0] << ' ' ; cout << i << '\n'; break; } } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...