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 long long maxn=1000+10;
long long all[maxn],vis[maxn],inf=1e9+5,n,m;
vector<long long>adj[maxn],dp[maxn],pd[maxn],fdp[maxn];
void dfsvis(long long u){
vis[u]=1;
for(auto x:adj[u]){
if(vis[x]==0){
dfsvis(x);
}
}
}
void vorod(){
cin>>n>>m;
all[n+1]=inf;
for(long long i=1;i<=n;i++){
cin>>all[i];
}
for(long long i=0;i<m;i++){
long long u,v;
cin>>u>>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
}
void pre(){
vector<long long>tof;
for(long long i=1;i<=n;i++){
if(vis[i]==0){
tof.push_back(i);
dfsvis(i);
}
}
for(auto x:tof){
adj[x].push_back(n+1);
adj[n+1].push_back(x);
}
}
void merge(long long u,long long v){
long long szu=(long long)dp[u].size(),szv=(long long)dp[v].size();
vector<long long>fake(szu+szv-1,inf),fakea(szu+szv-1,inf),fakefdp(szu+szv-1,inf);
for(long long i=0;i<szu;i++){
for(long long j=0;j<szv;j++){
fake[i+j]=min(fake[i+j],dp[u][i]+dp[v][j]);
fakea[i+j]=min(fakea[i+j],pd[u][i]+dp[v][j]);
fakefdp[i+j]=min(fakefdp[i+j],fdp[u][i]+dp[v][j]);
if(i<szu-1&&j<szv-1){
fake[i+j+2]=min(fake[i+j+2],fdp[u][i]+fdp[v][j]+all[u]+all[v]);
fakea[i+j+2]=min(fakea[i+j+2],fdp[u][i]+fdp[v][j]+all[u]+all[v]);
}
if(i<szu-1){
fake[i+j+1]=min(fake[i+j+1],fdp[u][i]+pd[v][j]+all[u]);
fakea[i+j+1]=min(fakea[i+j+1],fdp[u][i]+pd[v][j]+all[u]);
}
if(j<szv-1){
fake[i+j+1]=min(fake[i+j+1],pd[u][i]+fdp[v][j]+all[v]);
fakea[i+j+1]=min(fakea[i+j+1],pd[u][i]+fdp[v][j]+all[v]);
}
}
}
for(long long i=0;i<szu+szv-1;i++){
fake[i]=min(fake[i],min(fakea[i],fakefdp[i]));
}
for(int i=szu+szv-3;i>=0;i--){
fake[i]=min(fake[i],fake[i+1]);
fakea[i]=min(fakea[i],fakea[i+1]);
fakefdp[i]=min(fakefdp[i],fakefdp[i+1]);
}
dp[u].swap(fake);
pd[u].swap(fakea);
fdp[u].swap(fakefdp);
}
void solve(long long u,long long par=-1){
dp[u].resize(2);
pd[u].resize(2);
fdp[u].resize(2);
dp[u][1]=pd[u][1]=pd[u][0]=fdp[u][1]=inf;
for(auto x:adj[u]){
if(x==par){
continue;
}
solve(x,u);
merge(u,x);
}
/* cout<<"hey: "<<u<<endl;
for(auto x:dp[u]){
cout<<x<<" ";
}
cout<<"\n";
for(auto x:pd[u]){
cout<<x<<" ";
}
cout<<"\n";*/
}
void khor(){
long long u=n+1;
long long q;
cin>>q;
for(long long i=0;i<q;i++){
long long s;
cin>>s;
long long low=0,high=(long long)dp[u].size(),mid;
while(high-low>1){
mid=(high+low)>>1;
if(dp[u][mid]<=s){
low=mid;
}else{
high=mid;
}
}
cout<<low<<"\n";
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("inp.txt","r",stdin);
vorod();
pre();
solve(n+1,-1);
khor();
}
# | 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... |