Submission #1276895

#TimeUsernameProblemLanguageResultExecution timeMemory
1276895SmuggingSpunDžumbus (COCI19_dzumbus)C++20
0 / 110
253 ms3772 KiB
#include<bits/stdc++.h> #define taskname "C" using namespace std; typedef long long ll; const int lim = 1e3 + 5; const ll INF = 1e18; template<class T>void minimize(T& a, T b){ if(a > b){ a = b; } } int n, m, cnt[lim]; ll D[lim]; vector<int>g[lim]; bitset<lim>vis; vector<vector<ll>>dfs(int s){ cnt[s] = 1; vis[s] = true; vector<vector<ll>>dp(2, vector<ll>(2, INF)); dp[0][0] = 0; for(int& d : g[s]){ if(!vis[d]){ vector<vector<ll>>f = dfs(d); cnt[s] += cnt[d]; while(dp.size() <= cnt[s]){ dp.push_back(vector<ll>(2, INF)); } for(int i = cnt[s]; i > 0; i--){ for(int j = min(i, cnt[d]); j > 0; j--){ minimize(dp[i][0], dp[i - j][0] + min(f[j][0], f[j][1])); minimize(dp[i][1], dp[i - j][1] + min(f[j][0], f[j][1])); if(i > j + 1){ minimize(dp[i][1], dp[i - j - 2][0] + f[j][0] + D[s] + D[d]); } if(i > j){ minimize(dp[i][1], dp[i - j - 1][0] + f[j][1] + D[s]); } } minimize(dp[i][1], dp[i - 1][1] + D[d]); if(i > 1){ minimize(dp[i][1], dp[i - 2][0] + D[d] + D[s]); } } } } return dp; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if(fopen(taskname".inp", "r")){ freopen(taskname".inp", "r", stdin); } cin >> n >> m; for(int i = 1; i <= n; i++){ cin >> D[i]; } for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } vis.reset(); vector<ll>dp(n + 1, INF); dp[0] = 0; for(int i = 1; i <= n; i++){ if(!vis[i]){ vector<vector<ll>>f = dfs(i); for(int j = n; j > 0; j--){ for(int k = min(cnt[i], j); k > 0; k--){ minimize(dp[j], dp[j - k] + min(f[k][0], f[k][1])); } } } } int q; cin >> q; for(int _ = dp[1] = 0; _ < q; _++){ ll x; cin >> x; cout << (n == 1 || x < dp[2] ? 0 : upper_bound(dp.begin(), dp.end(), x) - dp.begin() - 1) << "\n"; } }

Compilation message (stderr)

dzumbus.cpp: In function 'int main()':
dzumbus.cpp:51:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...