Submission #312457

#TimeUsernameProblemLanguageResultExecution timeMemory
312457colazcyDžumbus (COCI19_dzumbus)C++17
110 / 110
77 ms22264 KiB
#include <cstdio> #include <cctype> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int maxn = 1e3 + 100; typedef long long ll; inline int read(){ int x = 0;char c = getchar(); while(!isdigit(c))c = getchar(); while(isdigit(c))x = x * 10 + c - '0',c = getchar(); return x; } int n,m,val[maxn],vis[maxn],siz[maxn]; vector<int> G[maxn]; inline void addedge(int u,int v){G[u].push_back(v);} int f[maxn][maxn][2][2],ans[maxn]; template <typename A,typename B> inline void chk(A &a,B b){ if(b >= 0x3f3f3f3f)b = 0x3f3f3f3f; if(b < a)a = b; } inline void dfs(int u){ siz[u] = 1; vis[u] = 1; f[u][0][1][0] = val[u]; f[u][0][0][0] = 0; for(int i = 0;i < G[u].size();i++){ int v = G[u][i]; if(vis[v])continue; dfs(v); for(int du = siz[u];du >= 0;du--) for(int optu1 = 0;optu1 < 2;optu1++) for(int optu2 = 0;optu2 < 2;optu2++) if(f[u][du][optu1][optu2] < 0x3f3f3f3f) for(int dv = 0;dv <= siz[v];dv++) for(int optv1 = 0;optv1 < 2;optv1++) for(int optv2 = 0;optv2 < 2;optv2++) chk(f[u][du + dv + (!optu2 + !optv2) * (optu1 && optv1)][optu1][optu2 || (optu1 && optv1)],f[u][du][optu1][optu2] + f[v][dv][optv1][optv2]); siz[u] += siz[v]; } } inline void init(){ memset(f,0x3f,sizeof(f)); memset(ans,0x3f,sizeof(ans)); ans[0] = 0; int sum = 0; for(int i = 1;i <= n;i++) if(!vis[i]){ dfs(i); for(int j = sum;j >= 0;j--) for(int k = 0;k <= siz[i];k++) chk(ans[j + k],ans[j] + min(min(f[i][k][0][0],f[i][k][0][1]),min(f[i][k][1][0],f[i][k][1][1]))); sum += siz[i]; } for(int i = n - 1;i >= 0;i--)ans[i] = min(ans[i],ans[i + 1]); } inline void solve(){ int s = read(); int l = 0,r = n,ans = 0; while(l <= r){ int mid = (l + r) >> 1; if(::ans[mid] <= s)ans = mid,l = mid + 1; else r = mid - 1; } printf("%d\n",ans); } int main(){ n = read(),m = read(); for(int i = 1;i <= n;i++)val[i] = read(); for(int u,v,i = 1;i <= m;i++) u = read(),v = read(),addedge(u,v),addedge(v,u); init(); int q = read(); while(q--)solve(); return 0; }

Compilation message (stderr)

dzumbus.cpp: In function 'void dfs(int)':
dzumbus.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i = 0;i < G[u].size();i++){
      |                ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...