#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN=2001;
const ll MAXK=1000001;
const ll INF = 1e9;
const ll MOD = 1e9+7;
vi dp1[MAXN]; // off
vi dp2[MAXN]; // on
vi dp3[MAXN]; // island
int sub[MAXN];
int A[MAXN];
vi V[MAXN];
int N,M,a,b;
int dpx[MAXN][2];
int dpy[MAXN][2];
void db(int x){
return;
cerr<<"Node "<<x<<'\n';
cerr<<"OFF: ";for(auto i:dp1[x])cout<<i<<' ';cout<<'\n';
cerr<<"ISLAND: ";for(auto i:dp2[x])cout<<i<<' ';cout<<'\n';
cerr<<"ON: ";for(auto i:dp3[x])cout<<i<<' ';cout<<'\n';
cerr<<'\n';
}
void dfs(int x,int p){
// cerr<<"Dfs "<<x<<' '<<p<<'\n';
sub[x]=1;
if(SZ(V[x])==1&&p!=-1){
dp1[x].pb(0);dp1[x].pb(INF);
dp2[x].pb(INF);dp2[x].pb(A[x]);
dp3[x].pb(INF);dp3[x].pb(INF);
db(x);
return;
}
vi child;
for(auto v:V[x])if(v!=p)child.pb(v);
for(auto i:child){dfs(i,x);sub[x]+=sub[i];}
// first we dp to find the optimal for OFF
for(int i=0;i<=sub[x];++i)dpx[i][0]=dpx[i][1]=INF;
int T=0;
dpx[0][0]=0;
int t=1;
for(auto i:child){
// cerr<<"Child "<<i<<' '<<sub[i]<<' '<<SZ(dp3[i])<<'\n';
for(int i=0;i<=T+sub[i];++i)dpx[i][t]=INF;
for(int c=0;c<=sub[i];++c){
int val=c;
int cst=min({dp1[i][c],dp3[i][c]});
for(int i=0;i<=T;++i){
int n=i+val;
int w=cst+dpx[i][1-t];
dpx[n][t]=min(w,dpx[n][t]);
}
}
T+=sub[i];
t=1^t;
}
for(int i=0;i<=T;++i)dp1[x].pb(dpx[i][t^1]);
dp1[x].pb(INF);
// dp to find the optimal for ON
for(int i=0;i<=sub[x];++i)dpx[i][0]=dpx[i][1]=INF;
for(int i=0;i<=sub[x];++i)dpy[i][0]=dpy[i][1]=INF;
T=0;t=1;
dpx[0][0]=0; // dpx[0] means not on
for(auto i:child){
for(int i=0;i<=T+sub[i];++i)dpx[i][t]=dpy[i][t]=INF;
for(int c=0;c<=sub[i];++c){
int val=c;
int csa=dp1[i][c];
int csb=min(dp2[i][c],dp3[i][c]);
for(int i=0;i<=T;++i){ // OFF to OFF
int n=i+val;
int w=csa+dpx[i][1^t];
dpx[n][t]=min(w,dpx[n][t]);
}
for(int i=0;i<=T;++i){ // OFF to ON
int n=i+val;
int w=csb+dpx[i][1^t];
dpy[n][t]=min(w,dpy[n][t]);
}
for(int i=0;i<=T;++i){ // ON to ON
int n=i+val;
int w=min(csa,csb)+dpy[i][1^t];
// cerr<<i<<" to "<<n<<' '<<dpy[i][1-t]<<' '<<w<<'\n';
dpy[n][t]=min(w,dpy[n][t]);
}
}
T+=sub[i];
t=1^t;
}
dp2[x].pb(INF);dp3[x].pb(INF);
for(int i=0;i<=T;++i)dp3[x].pb(dpy[i][t^1]+A[x]); // ON
for(int i=0;i<=T;++i)dp2[x].pb(dpx[i][t^1]+A[x]); // ISLAND
db(x);
}
int res[MAXN];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>N>>M;
for(int i=1;i<=N;++i)cin>>A[i];
for(int i=0;i<M;++i){
cin>>a>>b;V[a].pb(b);V[b].pb(a);
}
dfs(1,-1);
assert(sub[1]==N);
for(int i=1;i<=N;++i)res[i]=INF;
for(int i=0;i<=sub[1];++i){
res[i]=min(dp1[1][i],dp3[1][i]);
}
res[1]=res[2];
cin>>a;while(a--){
cin>>b;
int t=ub(res,res+sub[1],b)-res-1;
cout<<t<<'\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
10496 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
11904 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
10496 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
11904 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
2552 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
10496 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
11904 KB |
Output isn't correct |
