Submission #389029

#	Time	Username	Problem	Language	Result	Execution time	Memory
389029		ogibogi2004	Capital City (JOI20_capital_city)	C++14	100 / 100	941 ms	41924 KiB

capital_city

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=2e5+6;
int n,k;
int c[MAXN];
vector<int>g[MAXN];
vector<int>nodes[MAXN];
int used3[MAXN],t;
bool cantuse[MAXN];
int ans;
bool used[MAXN];
bool used1[MAXN];
bool used2[MAXN];
int subtree[MAXN],par[MAXN];
void dfs(int u,int p,int t)
{
	par[u]=p;
	used3[u]=t;
	subtree[u]=1;
	for(auto xd:g[u])
	{
		if(xd==p)continue;
		if(used[xd])continue;
		dfs(xd,u,t);
		subtree[u]+=subtree[xd];
	}
}
int find_centroid(int u,int p,int n1)
{
	for(auto xd:g[u])
	{
		if(xd==p)continue;
		if(used[xd])continue;
		if(subtree[xd]>n1/2)
		{
			return find_centroid(xd,u,n1);
		}
	}
	return u;
}
void solve(int u)
{
	t++;
	dfs(u,0,t);
	int cen=find_centroid(u,0,subtree[u]);
	dfs(cen,0,t);
	queue<int>q;
	//cout<<"&& "<<u<<" "<<cen<<endl;
	if(cantuse[c[cen]]==0)
	{
		bool imposibel=0;
		for(auto xd:nodes[c[cen]])
		{
			q.push(xd);
			if(used3[xd]!=t){imposibel=1;break;}
		}
		int cnt=1;
		vector<int>vc;
		vc.push_back(c[cen]);
		used2[c[cen]]=1;cantuse[c[cen]]=1;
		if(!imposibel)
		while(!q.empty())
		{
			u=q.front();q.pop();
			//cout<<u<<" ";
			used1[u]=1;
			if(par[u]==0)continue;
			if(used1[par[u]]==0&&used2[c[par[u]]]==0&&cantuse[c[par[u]]])
			{
				imposibel=1;
				break;
			}
			if(used2[c[par[u]]]==0)
			{
				//cout<<" *"<<c[par[u]]<<"* ";
				used2[c[par[u]]]=1;vc.push_back(c[par[u]]);
				cantuse[c[par[u]]]=1;
				for(auto xd:nodes[c[par[u]]])
				{
					if(used3[xd]!=t){imposibel=1;break;}
					q.push(xd);
				}
				cnt++;
			}
		}
		//cout<<endl;
		//cout<<imposibel<<" "<<cnt<<endl;
		if(!imposibel)ans=min(ans,cnt);
		for(auto xd:vc){used2[xd]=0;cantuse[xd]=0;}
	}
	used[cen]=1;
	for(auto xd:g[cen])
	{
		if(used[xd]==0)
		{
			solve(xd);
		}
	}
}
int main()
{
	cin>>n>>k;
	ans=k;
	for(int i=1;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(int i=1;i<=n;i++)
	{
		cin>>c[i];
		nodes[c[i]].push_back(i);
	}
	solve(1);
	cout<<ans-1<<endl;
return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 59 / 59