Submission #750321

#	Time	Username	Problem	Language	Result	Execution time	Memory
750321		Dan4Life	Capital City (JOI20_capital_city)	C++17	0 / 100	26 ms	17196 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)1e5+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);
}

/*
Root the tree at the centroid, and keep track of previous centroids 
(these vertices will be "blocked" in the tree).

We will consider a city, such that the current centroid is included in this city, 
and all "blocked" vertices and vertices below them must not be included.

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.

After this proccess terminates (there are no more colors that we must add), 
we will check if none of the added colors have vertices under "blocked" vertices, 
and if this is true we will minimize the answer with amountOfColorsAdded−1
.
*/

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 = 1;
		while(!Q.empty() and ok){
			auto a = Q.front(); Q.pop();
			int C = col[par[a]];
			if(vis[a]) ok=0;
			else if(!vis2[C]){
				for(auto u : v[C]) Q.push(u);
				vis2[C]=1; cnt++;
			}
		}
		if(ok) ans = min(ans, cnt-1);
	}
	vis[cen] = 1; 
	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