Submission #524620

#TimeUsernameProblemLanguageResultExecution timeMemory
524620DiriiDžumbus (COCI19_dzumbus)C++14
110 / 110
49 ms19032 KiB
// #pragma GCC target("avx2") // #pragma GCC optimize("Ofast") // #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #define ll long long #define cll const ll #define lp(a, b, c) for(ll a = b; a <= c; ++a) #define lpd(a, b, c) for(ll a = b; a >= c; --a) #define vec(a) vector<a> #define pp(a, b) pair<a, b> #define EACHCASE lpd(cs, read(), 1) #define Fname "f" using namespace std; template <typename T> inline void Read(T &x){ x = 0; char c; ll dau = 1; while(!isdigit(c = getchar())) if(c == '-') dau = -1; do{ x = x * 10 + c - '0'; } while (isdigit(c = getchar())); x *= dau; } ll read(){ ll tmp; cin >> tmp; return tmp; } void giuncute(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } void OF(){ if(fopen(Fname".inp", "r")){ freopen(Fname".inp", "r", stdin); freopen(Fname".out", "w", stdout); } else if(fopen(Fname".in", "r")){ freopen(Fname".in", "r", stdin); freopen(Fname".out", "w", stdout); } } cll mxn = 1e3 + 4; ll n, m, a[mxn], dp[mxn][mxn][2] = {{{0}}}, sz[mxn] = {0}, ans[mxn]; vec(ll) g[mxn]; void dfs(ll u, ll p){ sz[u] = 1; lp(i, 0, n) lp(j, 0, 1) dp[u][i][j] = 1e16; dp[u][0][0] = 0; // cerr << u << ' '; /* dp[u][sum][0] = min(dp[u][sum][0], min(dp[v][j][0], dp[v][j][1]) + dp[u][i][0]) dp[u][sum][1] = min({ dp[u][sum][1], min(dp[v][j][0], dp[v][j][1]) + dp[u][i][1], dp[v][j][1] + a[u] + dp[u][i - 1][0], dp[v][j - 1][0] + a[u] + a[v] + dp[u][i - 1][0] }) */ for(ll v : g[u]){ if(v == p) continue; dfs(v, u); lpd(i, sz[u], 0) lpd(j, sz[v], 0){ ll sum = i + j; dp[u][sum][0] = min(dp[u][sum][0], min(dp[v][j][0], dp[v][j][1]) + dp[u][i][0]); if(i) dp[u][sum][1] = min({ dp[u][sum][1], min(dp[v][j][0], dp[v][j][1]) + dp[u][i][1], dp[v][j][1] + a[u] + dp[u][i - 1][0] }); if(i && j) dp[u][sum][1] = min({ dp[u][sum][1], dp[v][j - 1][0] + a[u] + a[v] + dp[u][i - 1][0], dp[v][j - 1][0] + a[v] + dp[u][i][1] }); } sz[u] += sz[v]; } } int main(){ giuncute(); #ifndef ONLINE_JUDGE OF(); #endif cin >> n >> m; lp(i, 1, n) cin >> a[i]; lp(i, 1, m){ static ll u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } lp(i, 1, n) ans[i] = 1e16; ans[0] = 0; lp(i, 1, n) if(!sz[i]){ dfs(i, -1); lpd(tot, n, 2){ lp(j, 0, sz[i]){ if(tot < j) break; ans[tot] = min(ans[tot], min(dp[i][j][0], dp[i][j][1]) + ans[tot - j]); } } } // lp(i, 0, n) cerr << dp[1][i][0] << ' ' << dp[1][i][1] << ' ' << i << '\n'; // lp(i, 0, n) cerr << ans[i] << ' ' << i << '\n'; EACHCASE{ static ll s; cin >> s; ll l = 2, r = n, res = 0; while(l <= r){ ll mid = (l + r) >> 1; if(ans[mid] <= s) res = mid, l = mid + 1; else r = mid - 1; } cout << res << '\n'; } }

Compilation message (stderr)

dzumbus.cpp: In function 'void OF()':
dzumbus.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         freopen(Fname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(Fname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen(Fname".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dzumbus.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen(Fname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...