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;
#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second
const int mxn = 1010;
const ll inf = 1e9+10;
vector<int> tree[mxn];
ll dp[mxn][mxn][2];
ll arr[mxn];
int par[mxn];
int sz[mxn];
int n,m;
void init(int now){
for(auto nxt:tree[now]){
if(nxt == par[now])continue;
par[nxt] = now;
init(nxt);
}
return;
}
void dfs(int now){
sz[now] = 1;
for(auto &i:dp[now]){
for(auto &j:i)j = inf;
}
dp[now][0][0] = 0;
sz[now] = 1;
if(now == 0){
for(auto nxt:tree[now]){
if(nxt == par[now])continue;
dfs(nxt);
for(int i = sz[now];i>=0;i--){
for(int j = sz[nxt];j>=0;j--){
// cout<<now<<' '<<i<<' '<<j<<' '<<dp[now][i+j][0]<<' '<<dp[now][i][0]<<' '<<min(dp[nxt][j][0],dp[nxt][j][1])<<endl;
dp[now][i+j][0] = min({dp[now][i+j][0],dp[now][i][0]+min(dp[nxt][j][0],dp[nxt][j][1])});
}
}
sz[now] += sz[nxt];
}
return;
}
// dp[now][0][1] = arr[now];
for(auto nxt:tree[now]){
if(nxt == par[now])continue;
dfs(nxt);
for(int i = sz[now];i>=0;i--){
for(int j = sz[nxt];j>=0;j--){
// cout<<now<<" "<<nxt<<' '<<i<<' '<<j<<' '<<dp[now][i][0]<<' '<<dp[now][i][1]<<' '<<dp[nxt][j][0]<<' '<<dp[nxt][j][1]<<endl;
// dp[now][i+j][1] = min({dp[now][i+j][1],dp[now][i][1]+dp[nxt][j][0]});
dp[now][i+j+1][1] = min({dp[now][i+j+1][1],dp[now][i][0]+dp[nxt][j][1]+arr[now],dp[now][i][1]+dp[nxt][j][0]+arr[nxt]});
dp[now][i+j+2][1] = min({dp[now][i+j+2][1],dp[now][i][0]+dp[nxt][j][0]+arr[now]+arr[nxt]});
dp[now][i+j][0] = min({dp[now][i+j][0],dp[now][i][0]+min(dp[nxt][j][0],dp[nxt][j][1])});
dp[now][i+j][1] = min({dp[now][i+j][1],dp[now][i][1]+min(dp[nxt][j][1],dp[nxt][j][0])});
}
}
sz[now] += sz[nxt];
}
// cout<<now<<":"<<endl;
// for(int i = 0;i<=20;i++)cout<<dp[now][i][0]<<' ';cout<<endl;
// for(int i = 0;i<=20;i++)cout<<dp[now][i][1]<<' ';cout<<endl;
return;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i = 1;i<=n;i++)cin>>arr[i];
while(m--){
int a,b;
cin>>a>>b;
tree[a].push_back(b);
tree[b].push_back(a);
}
for(int i = 1;i<=n;i++){
if(!par[i]){
init(i);
tree[0].push_back(i);
}
}
dfs(0);
vector<pll> v;
v.push_back({0,0});
// for(int i = 0;i<20;i++)cout<<dp[0][i][0]<<',';cout<<endl;
for(int i = 1;i<mxn;i++)if(dp[0][i][0]<inf){
while(v.back().fs>=dp[0][i][0])v.pop_back();
v.push_back({dp[0][i][0],i});
}
// for(int i = 1;i<=n;i++){
// cout<<i<<":"<<arr[i]<<'\n';
// cout<<i<<":"<<sz[i]<<'\n';
// }
// for(auto &i:v){
// cout<<i.fs<<":"<<i.sc<<endl;
// }
int q;
cin>>q;
while(q--){
ll d;
cin>>d;
auto it = --upper_bound(v.begin(),v.end(),make_pair(d+1,-1LL));
cout<<(*it).second<<'\n';
}
return 0;
}
/*
14 13
2 3 4 19 20 21 5 22 6 7 23 8 10 14
1 2
1 3
1 4
2 5
2 6
3 7
3 8
3 9
4 10
8 11
10 13
10 12
12 14
3
45
44
23
*/
# | 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... |