oj.uz

Submission #250588

# Submission time Handle Problem Language Result Execution time Memory
250588 2020-07-18T13:01:12 Z dvdg6566 Džumbus (COCI19_dzumbus) C++14
110 / 110
 68 ms 13776 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=1001;
const ll MAXK=1000001;
const ll INF = 1e13;
const ll MOD = 1e9+7;

vi dp1[MAXN]; // off
vi dp2[MAXN]; // on
vi dp3[MAXN]; // island
ll sub[MAXN];
ll A[MAXN];
vi V[MAXN];
ll N,M,a,b;
ll dpx[MAXN][2];
ll dpy[MAXN][2];
ll dpz[MAXN][2];

void db(ll 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(ll x,ll 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(ll i=0;i<=sub[x];++i)dpx[i][0]=dpx[i][1]=INF;
	ll T=0;
	dpx[0][0]=0;
	ll t=1;
	for(auto i:child){
		// cerr<<"Child "<<i<<' '<<sub[i]<<' '<<SZ(dp3[i])<<'\n';
		for(ll i=0;i<=T+sub[i];++i)dpx[i][t]=INF;
		for(ll c=0;c<=sub[i];++c){
			ll val=c;
			ll cst=min({dp1[i][c],dp3[i][c]});
			for(ll i=0;i<=T;++i){
				ll n=i+val;
				ll w=cst+dpx[i][1-t];
				dpx[n][t]=min(w,dpx[n][t]);
			}
		}
		T+=sub[i];
		t=1^t;
	}
	for(ll i=0;i<=T;++i)dp1[x].pb(dpx[i][t^1]);
	dp1[x].pb(INF);

	// dp to find the optimal for ON
	for(ll i=0;i<=sub[x];++i)dpx[i][0]=dpx[i][1]=INF;
	for(ll 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(ll i=0;i<=T+sub[i];++i)dpx[i][t]=dpy[i][t]=INF;
		for(ll c=0;c<=sub[i];++c){
			ll val=c;
			ll csa=dp1[i][c];
			ll csb=min(dp2[i][c],dp3[i][c]);
			for(ll i=0;i<=T;++i){ // OFF to OFF
				ll n=i+val;
				ll w=csa+dpx[i][1^t];
				dpx[n][t]=min(w,dpx[n][t]);
			}
			for(ll i=0;i<=T;++i){ // OFF to ON
				ll n=i+val;
				ll w=csb+dpx[i][1^t];
				dpy[n][t]=min(w,dpy[n][t]);
			}
			for(ll i=0;i<=T;++i){ // ON to ON
				ll n=i+val;
				ll 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(ll i=0;i<=T;++i)dp3[x].pb(dpy[i][t^1]+A[x]); // ON
	for(ll i=0;i<=T;++i)dp2[x].pb(dpx[i][t^1]+A[x]); // ISLAND
	db(x);
}

ll res[MAXN];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>N>>M;
	for(ll i=1;i<=N;++i)cin>>A[i];
	for(ll i=0;i<M;++i){
		cin>>a>>b;V[a].pb(b);V[b].pb(a);
	}
	for(ll i=0;i<=N;++i)dpz[i][0]=dpz[i][1]=INF;
	ll T=0;
	dpz[0][0]=0;
	ll t=1;

	for(int x=1;x<=N;++x){
		if(SZ(dp1[x]))continue;

		dfs(x,-1);
		vi tm;

		for(int i=0;i<=sub[x];++i)tm.pb(min(dp1[x][i],dp3[x][i]));
		for(int i=sub[x]-1;i>=0;--i)tm[i]=min(tm[i],tm[i+1]);

		for(ll i=0;i<=T+sub[x];++i)dpz[i][t]=INF;
		for(ll c=0;c<=sub[x];++c){
			ll val=c;
			ll cst=tm[c];
			for(ll i=0;i<=T;++i){
				ll n=i+val;
				ll w=cst+dpz[i][1^t];
				dpz[n][t]=min(w,dpz[n][t]);
			}
		}
		T+=sub[x];
		// cerr<<t<<'\n';
		// for(int i=0;i<=T;++i)cout<<dpz[i][t]<<' ';cout<<'\n';
		t=1^t;
	}
	for(int i=0;i<=N;++i)res[i]=dpz[i][t^1];

	cin>>a;while(a--){
		cin>>b;
		ll t=ub(res,res+N+1,b)-res-1;
		cout<<t<<'\n';
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 10368 KB Output is correct
2 Correct 21 ms 11904 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 10368 KB Output is correct
2 Correct 21 ms 11904 KB Output is correct
3 Correct 62 ms 13776 KB Output is correct
4 Correct 68 ms 10876 KB Output is correct
5 Correct 62 ms 9212 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1408 KB Output is correct
2 Correct 41 ms 2296 KB Output is correct
3 Correct 44 ms 2808 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 10368 KB Output is correct
2 Correct 21 ms 11904 KB Output is correct
3 Correct 62 ms 13776 KB Output is correct
4 Correct 68 ms 10876 KB Output is correct
5 Correct 62 ms 9212 KB Output is correct
6 Correct 40 ms 1408 KB Output is correct
7 Correct 41 ms 2296 KB Output is correct
8 Correct 44 ms 2808 KB Output is correct
9 Correct 47 ms 3320 KB Output is correct
10 Correct 56 ms 3448 KB Output is correct
11 Correct 48 ms 3192 KB Output is correct