Submission #378322

#	Time	Username	Problem	Language	Result	Execution time	Memory
378322		iris2617	Capital City (JOI20_capital_city)	C++14	0 / 100	1412 ms	34540 KiB

capital_city

#include<bits/stdc++.h>
#define int long long
#define matsuri pair<int,int>
#define iris 1000000007
using namespace std;

vector<int> G[200010],aoi[200010];
int arr[200010];
int sz[200010],sum,x,pr[200010];
int v[200010],vv[200010],color[200010],tt;
queue<int> q;
bitset<200010> del;

void dfs2(int a,int f)
{
	pr[a]=f;
	for(int b:G[a])
	{
		if(b==f || del[b])
			continue;
		dfs2(b,a);
	}
}

int sana(int a)
{
	tt++;
	x=a;
	dfs2(x,0);
	
	int ans=0;
	bool flag=0;
	del[x]=1;
	vv[x]=tt;
	color[arr[x]]=1;
	q.push(arr[x]);
	while(!q.empty())
	{
		int k=q.front();
		q.pop();
		for(int a:aoi[k])
		{
			while(vv[a]!=tt)
			{
				vv[a]=tt;
				if(color[arr[a]]!=tt)
				{
					color[arr[a]]=tt;
					q.push(arr[a]);
					ans++;
				}
				a=pr[a];
			}
		}
	}
	if(flag)
		ans=1e9;
	
	return ans;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n,k,a,b,i,ans=1e9;
	
	cin>>n>>k;
	for(i=1;i<n;i++)
	{
		cin>>a>>b;
		G[a].emplace_back(b);
		G[b].emplace_back(a);
	}
	for(i=1;i<=n;i++)
	{
		cin>>a;
		arr[i]=a;
		aoi[a].emplace_back(i);
	}
	for(i=1;i<=n;i++)
	{
		ans=min(ans, sana(i));
	}
	cout<<ans<<'\n';
	
	return 0;
}

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