Submission #880771

#TimeUsernameProblemLanguageResultExecution timeMemory
880771lampoopppDžumbus (COCI19_dzumbus)C++17
0 / 110
25 ms9564 KiB
#include <bits/stdc++.h> using namespace std; const int inf = 1e9; const int N=1e3+100; vector<int> adj[N+1]; int d[N+1],n,m; bool avail[N+1]; int dp[2][N+1][N+1], sz[N+1]; void dfs(int u, int par) { avail[u]=1; for(int v : adj[u]) { if(v!=par) dfs(v, u); } } void solve(int x,int par) { sz[x]=1; for(int y:adj[x]) { if(y==par) continue; solve(y,x); for(int i=sz[x];i>=0;i--) { for(int j=sz[y];j>=0;j--) { dp[0][x][i+j]=min({dp[0][x][i+j],dp[0][x][i]+dp[1][y][j],dp[0][x][i]+dp[0][y][j]}); if(i>0) dp[1][x][i+j]=min(dp[1][x][i+j],dp[0][x][i-1]+dp[1][y][j]+d[x]); if(i>0&&j>0) dp[1][x][i+j]=min(dp[1][x][i+j],dp[0][x][i-1]+dp[0][y][j-1]+d[x]+d[y]); if(j>0) dp[1][x][i+j]=min(dp[1][x][i+j],dp[1][x][i]+dp[0][y][j-1]+d[y]); dp[1][x][i+j]=min({dp[1][x][i+j],dp[1][x][i]+dp[1][y][j],dp[1][x][i]+dp[0][y][j]}); } } sz[x]+=sz[y]; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n,m; cin >> n >> m; for(int i=1;i<=n;++i) cin >> d[i]; for(int i=1;i<=m;++i) { int u,v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } for(int i=1;i<=n;++i) { if(!avail[i]) {dfs(i, 0); adj[0].push_back(i);} } // cout << "K"; for(int i=0;i<=n;i++) { for(int j=1;j<=n;j++) { dp[0][i][j]=dp[1][i][j]=inf; } dp[1][i][0]=inf; } // cout << "K"; solve(0,0); int q; cin >> q; while(q--) { int s; cin >> s; for(int i=n;i>=1;--i) { if(dp[0][0][i]<=s) {cout << i << '\n'; break;} } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...