Submission #1217857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217857		emptypringlescan	Capital City (JOI20_capital_city)	C++17	100 / 100	584 ms	37076 KiB

capital_city

#include <bits/stdc++.h>
using namespace std;
int n,k;
vector<int> adj[200005];
int arr[200005],tot[200005];
int sz[200005],del[200005];
int dfssize(int x, int p){
	sz[x]=1;
	for(int i:adj[x]){
		if(i==p||del[i]) continue;
		sz[x]+=dfssize(i,x);
	}
	return sz[x];
}
int findcent(int x, int p, int tsz){
	for(int i:adj[x]){
		if(i==p||del[i]) continue;
		if(sz[i]*2>tsz) return findcent(i,x,tsz);
	}
	return x;
}
vector<int> grr[200005];
int par[200005],v[200005],vcol[200005];
int ans;
vector<int> undo;
void dfs(int x, int p){
	grr[arr[x]].push_back(x);
	undo.push_back(arr[x]);
	par[x]=p;
	v[x]=0;
	vcol[arr[x]]=0;
	for(int i:adj[x]){
		if(i==p||del[i]) continue;
		dfs(i,x);
	}
}
void build(int x){
	x=findcent(x,-1,dfssize(x,-1));
	dfs(x,-1);
	vector<int> q;
	q.push_back(x);
	bool can=true;
	int col=0;
	while(!q.empty()){
		int yay=q.back();
		q.pop_back();
		if(vcol[arr[yay]]) continue;
		vcol[arr[yay]]=1;
		col++;
		if((int)grr[arr[yay]].size()!=tot[arr[yay]]){
			can=false;
			break;
		}
		for(int i:grr[arr[yay]]){
			int cur=i;
			while(cur!=-1&&!v[cur]){
				q.push_back(cur);
				v[cur]=1;
				cur=par[cur];
			}
		}
	}
	if(can){
		ans=min(ans,col);
	}
	del[x]=1;
	for(int i:undo) grr[i].clear();
	undo.clear();
	for(int i:adj[x]){
		if(!del[i]) build(i);
	}
}
int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    for(int i=0; i<n-1; i++){
		int a,b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	for(int i=1; i<=n; i++){
		cin >> arr[i];
		tot[arr[i]]++;
	}
	ans=n;
	build(1);
	cout << ans-1;
}

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