Submission #847051

#TimeUsernameProblemLanguageResultExecution timeMemory
847051CookieDžumbus (COCI19_dzumbus)C++14
0 / 110
291 ms16216 KiB
#include<bits/stdc++.h> #define ll long long #define vt vector #define pb push_back #define pii pair<int, int> #define sz(v) (int)v.size() #define fi first #define se second using namespace std; const ll base = 107, mod = 1e9 + 7, mxv = 1e4 + 5, inf = 1e15; const int mxn = 1e3 + 5, N = 3e6 + 5; int n, m; ll d[mxn + 1]; ll dp[mxn + 1][mxn + 1][2]; bool vis[mxn + 1]; int sz[mxn + 1]; vt<int>adj[mxn + 1]; void dfs2(int s){ vis[s] = 1; for(auto i: adj[s]){ if(!vis[i]){ dfs2(i); } } } void ckmin(ll &a, ll b){ a = min(a, b); } void dfs(int s, int pre){ dp[s][0][0] = 0; sz[s] = 1; for(auto i: adj[s]){ if(i != pre){ dfs(i, s); for(int j = sz[s] + sz[i]; j >= 1; j--){ for(int k = 0; k <= min(sz[i], j); k++){ ckmin(dp[s][j][0], dp[s][j - k][0] + min(dp[i][k][1], dp[i][k][0])); } } for(int j = sz[s] + sz[i]; j >= 1; j--){ for(int k = 0; k <= min(sz[i], j); k++){ ckmin(dp[s][j][1], dp[s][j - k][1] + min(dp[i][k][0], d[s] + dp[i][k][1])); if(j - k >= 1){ // connect s (off) = i(on) ckmin(dp[s][j][1], dp[s][j - k - 1][0] + d[s] + dp[i][k][1]); }if(j - k >= 1 && k >= 1){ // connect s to i (both off) ckmin(dp[s][j][1], dp[s][j - k - 1][0] + d[s] + d[i] + dp[i][k - 1][0]); }if(k >= 1){ // connect active s to off i ckmin(dp[s][j][1], dp[s][j - k][1] + d[s] + d[i] + dp[i][k - 1][0]); } } } sz[s] += sz[i]; } } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; d[0] = inf; for(int i = 1; i <= n; i++)cin >> d[i]; for(int i = 0; i <= n; i++){ for(int j = 0; j <= n; j++){ dp[i][j][0] = dp[i][j][1] = inf; } } for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } for(int i = 1; i <= n; i++){ if(!vis[i]){ dfs2(i); adj[0].pb(i); } } dfs(0, -1); int q; cin >> q; vt<ll>comp; for(int i = 0; i <= n; i++){ comp.pb(min(dp[0][i][0], dp[0][i][1])); } while(q--){ ll s; cin >> s; int id = upper_bound(comp.begin(), comp.end(), s) - comp.begin() - 1; cout << id << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...