Submission #750348

#	Time	Username	Problem	Language	Result	Execution time	Memory
750348		Dan4Life	Capital City (JOI20_capital_city)	C++17	0 / 100	171 ms	34736 KiB

capital_city

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(a) begin(a),end(a)
const int mxN = (int)2e5+2;

vector<int> v[mxN];
int n, m, ans = mxN;
int col[mxN], sub[mxN], par[mxN], vis[mxN], vis2[mxN];
vector<int> adj[mxN];

int getSub(int s, int p){
	sub[s] = 1; par[s]=p;
	for(auto u : adj[s])
		if(u!=p and !vis[u]) sub[s]+=getSub(u,s);
	return sub[s];
}

int findCen(int s, int p, int n){
	for(auto u : adj[s])
		if(u!=p and !vis[u] and sub[u]>n/2)
			return findCen(u,s,n);
	return s;
}

void dfs(int s, int p){
	par[s] = p;
	for(auto u : adj[s])
		if(u!=p and !vis[u]) dfs(u,s);
}

/*
To construct this city, we take all vertices that have the same color as the centroid, 
check their parents in the tree, and if the parent has a different color, 
we will repeat the same proccess with that color. This can be done efficiently with a queue.
*/

void cenDec(int cen, int p){
	cen = findCen(cen,p,getSub(cen,cen)); 
	if(!vis2[col[cen]]){
		queue<int> Q = queue<int>(); Q.push(cen);
		bool ok = 1; int cnt = 0;
		while(!Q.empty() and ok){
			auto a = Q.front(); Q.pop(); vis[a]=1;
			int C = col[a];
			if(!vis2[C]){
				for(auto u : v[C]) if(col[par[u]]!=C) Q.push(par[u]);
				vis2[C]=1; cnt++;
			}
		}
		if(ok) ans = min(ans, cnt);
	}
	for(auto u : adj[cen])
		if(u!=p and !vis[u]) cenDec(u,cen);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m; 
	for(int i = 1; i < n; i++){
		int a, b; cin >> a >> b;
		adj[a].pb(b), adj[b].pb(a);
	}
	for(int i = 1; i <= n; i++) cin >> col[i], v[col[i]].pb(i);
	cenDec(1,-1); cout << ans << "\n";
}

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