oj.uz

Submission #205645

# Submission time Handle Problem Language Result Execution time Memory
205645 2020-02-29T11:17:59 Z mraron Džumbus (COCI19_dzumbus) C++14
110 / 110
 794 ms 34296 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int> adj[1111];
int b0[1111];
ll s[1111];
void dfs0(int x){
	b0[x]=1;
	for(auto i:adj[x]) {
		if(!b0[i]) dfs0(i);
	}
}

//0 -> not choosen
//1 -> choosen alone
//2 -> choosen with group
ll dp[1002][1002][3];
int b1[1111];
int sz[1111];
int dfs1(int x) {
	b1[x]=1;
	vector<int> lst;
	sz[x]=1;
	for(auto i:adj[x]) {
		if(!b1[i]) {
			sz[x]+=dfs1(i);
			lst.push_back(i);
		}
	}
	
	if(lst.empty()) {
		dp[x][1][1]=s[x];
		dp[x][0][0]=0;
		return sz[x];
	}
	ll dp2[lst.size()+1][sz[x]+1][3];
	memset(dp2, 0x0F, sizeof dp2);
	dp2[0][0][0]=0;
	dp2[0][1][1]=s[x];
	int eddig=1;
	for(int i=1;i<(int)lst.size()+1;++i) {
		for(int j=0;j<=eddig;++j) {
			for(int k=0;k<=sz[lst[i-1]];++k) {
				for(int l=0;l<3;++l) 
					dp2[i][j+k][l]=min(dp2[i][j+k][l], dp2[i-1][j+k][l]);
				dp2[i][j+k][0]=min(dp2[i][j+k][0], dp2[i-1][j][0]+min(dp[lst[i-1]][k][0], dp[lst[i-1]][k][2]));
				dp2[i][j+k][1]=min(dp2[i][j+k][1], dp2[i-1][j][1]+dp[lst[i-1]][k][0]);
				dp2[i][j+k][2]=min(dp2[i][j+k][2], dp2[i-1][j][2]+dp[lst[i-1]][k][0]);
				dp2[i][j+k][2]=min(dp2[i][j+k][2], min(dp2[i-1][j][2], dp2[i-1][j][1])+min(dp[lst[i-1]][k][1], dp[lst[i-1]][k][2]));
				
			}
		}
		eddig+=sz[lst[i-1]];
	}
	for(int i=0;i<=eddig;++i) {
		for(int j=0;j<3;++j) {
			dp[x][i][j]=dp2[lst.size()][i][j];
		}
	}
	
	return sz[x];
}


int main() {
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;++i) cin>>s[i];
	for(int i=0;i<m;++i) {
		int a,b;
		cin>>a>>b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	
	int root=n+1;
	for(int i=1;i<=n;++i) {
		if(!b0[i]) {
			adj[root].push_back(i);
			adj[i].push_back(root);
			dfs0(i);
		}
	}
	memset(dp,0x0F,sizeof dp);
	dfs1(root);
	int q;
	cin>>q;
	//cerr<<dp[1][8][2]<<"\n";
	
	while(q--) {
		int x;
		cin>>x;
		int ans=0;
		for(int i=0;i<=n;++i) {
			if(dp[root][i][0]<=x) {
				ans=max(ans, i);
			}
		}
		cout<<ans<<"\n";
	}
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24184 KB Output is correct
2 Correct 32 ms 24184 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24184 KB Output is correct
2 Correct 32 ms 24184 KB Output is correct
3 Correct 781 ms 26380 KB Output is correct
4 Correct 787 ms 27000 KB Output is correct
5 Correct 750 ms 26488 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 26232 KB Output is correct
2 Correct 565 ms 25828 KB Output is correct
3 Correct 573 ms 26488 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24184 KB Output is correct
2 Correct 32 ms 24184 KB Output is correct
3 Correct 781 ms 26380 KB Output is correct
4 Correct 787 ms 27000 KB Output is correct
5 Correct 750 ms 26488 KB Output is correct
6 Correct 558 ms 26232 KB Output is correct
7 Correct 565 ms 25828 KB Output is correct
8 Correct 573 ms 26488 KB Output is correct
9 Correct 794 ms 26772 KB Output is correct
10 Correct 792 ms 30584 KB Output is correct
11 Correct 794 ms 34296 KB Output is correct