Submission #894867

#	Time	Username	Problem	Language	Result	Execution time	Memory
894867		vjudge1	Mergers (JOI19_mergers)	C++17	10 / 100	101 ms	1104 KiB

mergers

#include <bits/stdc++.h>
using namespace std;
const int mxn=1e2+5;
int n,k,mark[8],comp[8],par[mxn],s[mxn],ans=10,sum[mxn][8],sz[8],szz[8];
vector<int>v[mxn];
bool dfs(int z,int x){
	bool res=1;
	for(int j=1;j<=x;j++)
		sum[z][j]=0;
	sum[z][comp[s[z]]]++;
	for(auto i:v[z]){
		if(par[z]!=i){
			par[i]=z;
			res&=dfs(i,x);
			for(int j=1;j<=x;j++)
				sum[z][j]+=sum[i][j];
		}
	}
	bool cnt=1;
	for(int j=1;j<=x;j++){
		if(sum[z][j]==szz[j] || sum[z][j]==0)cnt=1;
		else{
			cnt=0;
			break;
		} 
	}
	if(cnt && z!=1)return 0;
	return res;
}
void solve(int i,int x){
	if(i>k){
		for(int j=1;j<=x;j++){
			if(!mark[j])return ;
		}

		if(dfs(1,x)){
			ans=min(ans,k-x);
		}
		return ;
	}
	for(int j=1;j<=x;j++){
		comp[i]=j;
		mark[j]++;
		szz[j]+=sz[i];
		solve(i+1,x);
		mark[j]--;
		szz[j]-=sz[i];
	}
}
int main(){
	cin>>n>>k;
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		cin>>s[i];
		sz[s[i]]++;
	}
	for(int i=k;i>=1;i--){
		solve(1,i);
	}
	cout<<ans<<endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 24
• Subtask 3: 0 / 14
• Subtask 4: 0 / 22
• Subtask 5: 0 / 30