Submission #164414

#	Time	Username	Problem	Language	Result	Execution time	Memory
164414		tneluccus	Mergers (JOI19_mergers)	C++14	100 / 100	1880 ms	136932 KiB

mergers

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+2;
const int LOG=20;
int color[N],tin[N],tout[N],now=0,level[N],ancestor[N][LOG],head[N],cnt[N],deg[N];
vector<int> adj[N],lis[N];
int findd(int x){
	if(head[x]<0){
		return x;
	}
	int y=findd(head[x]);
	head[x]=y;
	return y;
}
void unionn(int x,int y){
	x=findd(x),y=findd(y);
	head[x]+=head[y];
	head[y]=x;
}
bool samee(int x,int y){
	return findd(x)==findd(y);
}
void dfs(int x,int p){
	now++;
	tin[x]=now;
	for(int i=1;i<LOG;i++){
		ancestor[x][i]=ancestor[ancestor[x][i-1]][i-1];
	}
	for(int i:adj[x]){
		if(i!=p){
			level[i]=level[x]+1;
			ancestor[i][0]=x;
			dfs(i,x);
		}
	}
	tout[x]=now;
}
int fin(int x,int y){
	while(y){
		int k=__lg(y);
		x=ancestor[x][k];
		y-=(1<<k);
	}
	return x;
}
int LCA(int x,int y){
	if(level[x]>level[y]){
		x=fin(x,level[x]-level[y]);
	}
	y=fin(y,level[y]-level[x]);
	if(x==y){
		return x;
	}
	for(int i=LOG-1;i>-1;i--){
		if(ancestor[x][i]!=ancestor[y][i]){
			x=ancestor[x][i],y=ancestor[y][i];
		}
	}
	return ancestor[x][0];
}
bool cmp(int x,int y){
	return tin[x]<tin[y];
}
void dfs1(int x,int p){
	for(int i:adj[x]){
		if(i!=p){
			dfs1(i,x);
			cnt[x]+=cnt[i];
		}
	}
	if(cnt[x]&&x!=p){
		unionn(x,p);
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m,i,j,k,l,num,ans=0;
	cin>>n>>num;
	for(i=1;i<n;i++){
		cin>>j>>k;
		adj[j].push_back(k);
		adj[k].push_back(j);
	}
	for(i=1;i<=n;i++){
		head[i]=-1;
		cin>>color[i];
		lis[color[i]].push_back(i);
	}
	dfs(1,1);
	for(i=1;i<=num;i++){
		sort(lis[i].begin(),lis[i].end(),cmp);
		int sz=lis[i].size();
		for(j=1;j<sz;j++){
			k=LCA(lis[i][j-1],lis[i][j]);
			lis[i].push_back(k);
		}
		sort(lis[i].begin(),lis[i].end(),cmp);
		lis[i].erase(unique(lis[i].begin(),lis[i].end()),lis[i].end());
		for(j=1;j<lis[i].size();j++){
			k=LCA(lis[i][j-1],lis[i][j]);
			cnt[lis[i][j]]++;
			cnt[k]--;
		}
	}
	dfs1(1,1);
	for(i=1;i<=n;i++){
		for(j=0;j<adj[i].size();j++){
			if(findd(i)!=findd(adj[i][j])){
				deg[findd(i)]++;
				deg[findd(adj[i][j])]++;
			}
		}
	}
	for(i=1;i<=n;i++){
		if(findd(i)==i){
			if(deg[i]==2){
				ans++;
			}
		}
	}
	cout<<(ans+1)/2;
}

Compilation message (stderr)

mergers.cpp: In function 'int main()':
mergers.cpp:100:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=1;j<lis[i].size();j++){
           ~^~~~~~~~~~~~~~
mergers.cpp:108:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<adj[i].size();j++){
           ~^~~~~~~~~~~~~~
mergers.cpp:78:8: warning: unused variable 'm' [-Wunused-variable]
  int n,m,i,j,k,l,num,ans=0;
        ^
mergers.cpp:78:16: warning: unused variable 'l' [-Wunused-variable]
  int n,m,i,j,k,l,num,ans=0;
                ^

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