Submission #378255

#	Time	Username	Problem	Language	Result	Execution time	Memory
378255		iris2617	Capital City (JOI20_capital_city)	C++14	1 / 100	790 ms	47244 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 dfs(int a)
{
	v[a]=tt;
	sz[a]=1;
	for(int b:G[a])
	{
		if(v[b]==tt || del[b])
			continue;
		dfs(b);
		sz[a]+=sz[b];
	}
}

void dc(int a,int f)
{
	int ouo=0;
	for(int b:G[a])
	{
		if(b==f || del[b])
			continue;
		dc(b,a);
		ouo=max(ouo, sz[b]);
	}
	ouo=max(ouo, sum-sz[a]);
	if(ouo<=sum/2)
		x=a;
}

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++;
	dfs(a);
	sum=sz[a];
	dc(a,0);
	dfs2(x,0);
	assert(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])
		{
			if(v[a]!=tt)
			{
				flag=1;
				break;
			}
			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;
//	cout<<' '<<x<<' '<<ans<<'\n';
	
	for(int b:G[x])
	{
		if(del[b])
			continue;
		ans=min(ans, sana(b));
	}
	return ans;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n,k,a,b,i;
	
	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);
	}
	cout<<sana(1)<<'\n';
	
	return 0;
}

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