Submission #251518

#TimeUsernameProblemLanguageResultExecution timeMemory
251518MrRobot_28Džumbus (COCI19_dzumbus)C++17
0 / 110
41 ms16256 KiB
#include<bits/stdc++.h> using namespace std; #define int long long int n, m; vector <int> d; vector <vector <int> > dp0, dp1, g; vector <bool> used; vector <int> sz; void dfs(int v, int p = -1) { used[v] = true; int allsz = 0; dp0[v][0] = 0; sz[v] = 1; int y = g[v].size(); for(int i = 0; i < y; i++) { int to = g[v][i]; if(to != p) { dfs(to, v); sz[v] += sz[to]; for(int k = allsz; k >= 0; k--) { for(int j = 0; j <= sz[to]; j++) { if(j != 1) { dp0[v][k + j] = min(dp0[v][k + j], dp0[v][k] + min(dp1[to][j], dp0[to][j])); } } } allsz += sz[to]; } } allsz = 1; dp1[v][1] = d[v]; for(int i = 0; i < y; i++) { int to = g[v][i]; if(to != p) { for(int k = allsz; k >= 0; k--) { for(int j = 1; j <= sz[to]; j++) { dp1[v][k + j] = min(dp1[v][k + j], dp1[v][k] + dp1[to][j]); dp1[v][k + j] = min(dp1[v][k + j], dp1[v][k] + dp0[to][j]); } } allsz += sz[to]; } } } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; d.resize(n); sz.resize(n); g.resize(n); used.resize(n); dp0.resize(n, vector <int> (n + 1, 1e18)); dp1.resize(n, vector <int> (n + 1, 1e18)); for(int i = 0; i < n; i++) { cin >> d[i]; } for(int i = 0; i < m; i++) { int a, b; cin >> a >> b; a--; b--; g[a].push_back(b); g[b].push_back(a); } vector <int> alldp(n + 1, 1e18); alldp[0] = 0; for(int i = 0; i < n; i++) { if(!used[i]) { dfs(i); for(int k = n; k >= 0; k--) { for(int j = 2; j <= sz[i] && k + j <= n; j++) { alldp[k + j] = min(alldp[j + k], alldp[k] + min(dp0[i][j], dp1[i][j])); } } } } alldp[1] = 0; int q; cin >> q; while(q--) { int s; cin >> s; int l = 0, r= n + 1; while(r - l > 1) { int midd = (r + l) / 2; if(alldp[midd] <= s) { l = midd; } else { r = midd; } } if(l == 1) { l = 0; } cout << l << "\n"; } 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...