Submission #250566

# Submission time Handle Problem Language Result Execution time Memory
250566 2020-07-18T11:28:10 Z dvdg6566 Džumbus (COCI19_dzumbus) C++14
0 / 110
47 ms 11904 KB
#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