Submission #250588

#	Time	Username	Problem	Language	Result	Execution time	Memory
250588		dvdg6566	Džumbus (COCI19_dzumbus)	C++14	110 / 110	68 ms	13776 KiB

dzumbus

#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 / 20
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30