Submission #954797

#	Time	Username	Problem	Language	Result	Execution time	Memory
954797		LCJLY	Capital City (JOI20_capital_city)	C++14	100 / 100	605 ms	47124 KiB

capital_city

#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,pii>pi2;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

vector<int>adj[200005];

int sz[200005];
int lvl[200005];
int color[200005];
int visited[200005];
int ptr=1;
vector<int>storage[200005];
int pp[200005];

void dfs(int index, int par, int l){
	sz[index]=1;
	visited[index]=ptr;
	for(auto it:adj[index]){
		if(lvl[it]!=-1) continue;
		if(it==par) continue;
		pp[it]=index;
		dfs(it,index,l);
		sz[index]+=sz[it];
	}
}

int dfs2(int index, int par, int n){
	for(auto it:adj[index]){
		if(lvl[it]!=-1) continue;
		if(it!=par&&sz[it]>n/2){
			return dfs2(it,index,n);
		}
	}
	return index;
}

int n,k;
int ans=0;

void dp(int index, int hold){
	queue<int>q;
	unordered_set<int>se;
	se.insert(color[index]);
	for(auto it:storage[color[index]]){
		if(visited[it]!=hold) return;
		if(it==index) continue;
		q.push(it);
	}
	
	while(!q.empty()){
		int cur=q.front();
		q.pop();
		int nxt=pp[cur];
		if(se.find(color[nxt])!=se.end()) continue;
		se.insert(color[nxt]);
		for(auto it:storage[color[nxt]]){
			if(visited[it]!=hold) return;
			q.push(it);
		}
	}	
	//show4(se,se);
	ans=min(ans,(int)se.size()-1);
}

void build(int index, int par, int l){
	dfs(index,par,l);
	int k=sz[index];
	int cent=dfs2(index,par,k);
	if(par==-1) par=cent;
	dfs(cent,-1,l);
	//show(cent,cent);
	dp(cent,ptr);
	lvl[cent]=l;	
	for(auto it:adj[cent]){
		if(lvl[it]!=-1) continue;
		ptr++;
		build(it,cent,l+1);
	}
}

void solve(){
	cin >> n >> k;
	int temp,temp2;
	ans=k;
	
	for(int x=0;x<n-1;x++){
		cin >> temp >> temp2;
		adj[temp].push_back(temp2);
		adj[temp2].push_back(temp);
	}	
	
	for(int x=1;x<=n;x++){
		cin >> color[x];
		storage[color[x]].push_back(x);
	}
	
	memset(lvl,-1,sizeof(lvl));
	build(1,-1,0);
	
	cout << ans;
}	
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

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