Submission #894768

#	Time	Username	Problem	Language	Result	Execution time	Memory
894768		amirhoseinfar1385	Mergers (JOI19_mergers)	C++17	100 / 100	843 ms	140288 KiB

mergers

#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10;
vector<int>adj[maxn];
map<int,int>mp[maxn];
int cntc[maxn],sz[maxn],n,k,val[maxn],cnt[maxn],res;

bool cmp(int a,int b){
	return sz[a]>sz[b];
}

void pre(int u=1,int par=0){
	if(u!=1){
		sort(adj[u].begin(),adj[u].end());
		adj[u].erase(lower_bound(adj[u].begin(),adj[u].end(),par));
	}
	sz[u]=1;
	for(auto x:adj[u]){
		pre(x,u);
		sz[u]+=sz[x];
	}
	sort(adj[u].begin(),adj[u].end(),cmp);
}
void solve(int u){
	if((int)adj[u].size()==0){
		if(cntc[val[u]]!=1){
			mp[u][val[u]]=1;
		}
		else{
			res++;
			cnt[u]=1;
		}
		return ;
	}
	solve(adj[u][0]);
	cnt[u]=cnt[adj[u][0]];
	swap(mp[adj[u][0]],mp[u]);
	for(int i=1;i<(int)adj[u].size();i++){
		solve(adj[u][i]);
		cnt[u]+=cnt[adj[u][i]];
		for(auto x:mp[adj[u][i]]){
			mp[u][x.first]+=x.second;
			if(cntc[x.first]==mp[u][x.first]){
				mp[u].erase(x.first);
			}
		}
	}
	mp[u][val[u]]++;
	if(cntc[val[u]]==mp[u][val[u]]){
		mp[u].erase(val[u]);
	}
	if((int)mp[u].size()==0){
		if(u!=1){
			if(cnt[u]==0){
				res++;
			}
			cnt[u]=1;
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	for(int i=0;i<n-1;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		cin>>val[i];
		cntc[val[i]]++;
	}
	pre(1);
	solve(1);
	if(cnt[1]==1){
		res++;
	}
	if(n==1){
		cout<<0<<"\n";
		return 0;
	}
	cout<<((res+1)/2)<<"\n";
}

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