Submission #1312878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312878		namhh	Capital City (JOI20_capital_city)	C++20	100 / 100	378 ms	38008 KiB

capital_city

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e5+5;
int n,k,a[N],sum[N],sz[N],check[N],del[N],par[N],vis[N],ans = 1e9;
vector<int>adj[N],loj,col[N];
int dfs(int u, int p){
	sz[u] = 1;
	for(int v: adj[u]){
		if(v != p && !del[v]){
			dfs(v,u);
			sz[u] += sz[v];
		}
	}
	return sz[u];
}
int find_centroid(int u, int p, int tot){
	for(int v: adj[u]){
		if(v != p && !del[v] && sz[v] > tot/2) return find_centroid(v,u,tot);
	}
	return u;
}
void get(int u, int p, int mau){
	loj.push_back(u);
	par[u] = p;
	for(int v: adj[u]){
		if(v != p && !del[v]) get(v,u,mau);
	}
}
void decompose(int u){
	int cent = find_centroid(u,0,dfs(u,0));
	loj.push_back(cent);
	par[cent] = 0;
	del[cent] = 1;
	for(int v: adj[cent]){
		if(!del[v]) get(v,cent,a[cent]);
	}
	int res = 0;
	for(int v: loj) col[a[v]].push_back(v);
	queue<int>q;
	q.push(a[cent]);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		if(check[u]) continue;
		if(col[u].size() < sum[u]){
			res = 1e9;
			break;
		}
		check[u] = 1;
		res++;
		for(int v: col[u]){
			int du = v;
			while(du != 0 && !vis[du]){
				vis[du] = 1;
				q.push(a[du]);
				du = par[du];
			}
		}
	}
	ans = min(ans,res-1);
	for(int v: loj){
		check[a[v]] = 0;
		vis[v] = 0;
		col[a[v]].clear();
	}
	loj.clear();
	for(int v: adj[cent]){
		if(!del[v]) decompose(v);
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> k;
	for(int i = 1; i < n; i++){
		int u,v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		sum[a[i]]++;
	}
	decompose(1);
	cout << ans;
}

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