Submission #899869

#	Time	Username	Problem	Language	Result	Execution time	Memory
899869		PM1	Mergers (JOI19_mergers)	C++17	0 / 100	106 ms	49584 KiB

mergers

#include <bits/stdc++.h>
using namespace std;
const int mxn=5e5+5;
int n,par[mxn][22],num[mxn],k,s[mxn],st[mxn],fn[mxn],cnt=0,sz[mxn],comp[mxn],ans=0;
bool marky[mxn];
struct yall{
	int u,uu;
}yal[mxn];
vector<int>v[mxn],act[mxn];
void pre(int z){
	st[z]=++cnt;
	act[s[z]].push_back(z);
	for(int i=1;i<=21;i++)
		par[z][i]=par[par[z][i-1]][i-1];
	for(auto i:v[z]){
		int x=yal[i].u^yal[i].uu^z;
		if(par[z][0]!=x){
			par[x][0]=z;
			pre(x);
		}
	}
	fn[z]=cnt;
}
int lca(int x,int y){
	if(st[x]<=st[y] && fn[x]>=fn[y])return x;
	for(int i=21;i>=0;i--){
		if(par[x][i]==0)continue;
		if(st[par[x][i]]>st[y] || fn[par[x][i]]<st[y])x=par[x][i];
	}
	return par[x][0];
}
void dfs(int z,int y=0){
	int res=0;
	for(auto i:v[z]){
		int x=yal[i].u^yal[i].uu^z;
		if(x!=par[z][0]){
			dfs(x,i);
			num[z]+=num[x];
		}
	}
	if(num[z]==0)
		marky[y]=1;
}
void fds(int z){
	comp[z]=cnt;
	for(auto i:v[z]){
		int x=yal[i].u^yal[i].uu^z;
		if(!comp[x] && !marky[i])
			fds(x);
	}
}
int main(){
	cin>>n>>k;
	for(int i=1;i<n;i++){
		cin>>yal[i].u>>yal[i].uu;
		v[yal[i].u].push_back(i);
		v[yal[i].uu].push_back(i);
	}
	for(int i=1;i<=n;i++)
		cin>>s[i];
	pre(1);
	for(int i=1;i<=k;i++){
			int x=act[i][0];
			for(int j=1;j<act[i].size();j++){
				x=lca(x,act[i][j]);
				num[x]++;
			}
			num[x]++;
	}
	dfs(1);
	cnt=1;
	for(int i=1;i<=n;i++){
		if(!comp[i]){
			fds(i);
			cnt++;
		}
	}
	for(int i=1;i<n;i++){
		if(marky[i]){
			sz[comp[yal[i].u]]++;
			sz[comp[yal[i].uu]]++;
		}
	}
	for(int i=1;i<=cnt;i++){
		if(sz[i]==1)ans++;
	}
	if(ans==1 || cnt<=2)
		cout<<0<<'\n';
	else
		cout<<(ans+1)/2<<endl;
}

Compilation message (stderr)

mergers.cpp: In function 'void dfs(int, int)':
mergers.cpp:33:6: warning: unused variable 'res' [-Wunused-variable]
   33 |  int res=0;
      |      ^~~
mergers.cpp: In function 'int main()':
mergers.cpp:64:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |    for(int j=1;j<act[i].size();j++){
      |                ~^~~~~~~~~~~~~~

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