This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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[N+1][N+1][2], 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 u, int par)
{
dp[u][0][1]=d[u];
dp[u][0][0]=0;
sz[u]=1;
for(int v : adj[u])
{
if(v!=par)
{
solve(v,u);
for(int j = sz[u]; j>=0;--j)
{
for(int k = sz[v]; k >=0;--k)
{
dp[u][j+k][0] = min(dp[u][j+k][0], dp[u][j][0] + min(dp[v][k][1], dp[v][k][0]));
if(j>0) dp[u][j+k][1] = min(dp[u][j+k][1], dp[u][j-1][1] + dp[v][k][1]);
if(k>0) dp[u][j+k][1] = min(dp[u][j+k][1], dp[u][j][1] + dp[v][k-1][1]);
if(j>0 && k>0) dp[u][j+k][1] = min(dp[u][j+k][1], dp[u][j-1][0] + dp[v][k-1][0]+d[u]+d[v]);
dp[u][j+k][1] = min(dp[u][j+k][1], dp[u][j][1] + dp[v][k][0]);
}
}
}
sz[u]+=sz[v];
}
}
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);
}
for(int i=0;i<=1000;++i)
{
for(int j=0;j<=1000;++j)
{
dp[i][j][0]=dp[i][j][1]=inf;
}
}
solve(0,0);
int q;
cin >> q;
while(q--)
{
int s;
cin >> s;
for(int i=m;i>=0;--i)
{
if(dp[0][i][0]<=s) {cout << i << '\n'; break;}
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |