Submission #750355

#	Time	Username	Problem	Language	Result	Execution time	Memory
750355		Dan4Life	Capital City (JOI20_capital_city)	C++17	100 / 100	2376 ms	38836 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, bool ok){
	par[s] = ok?p:-1;
	if(ok) vis2[col[s]]=0;
	for(auto u : adj[s])
		if(u!=p and !vis[u]) dfs(u,s,ok);
}

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

Compilation message (stderr)

capital_city.cpp: In function 'void cenDec(int, int)':
capital_city.cpp:50:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   50 |    if(ok) vis2[Cp]=1; cnt++;
      |    ^~
capital_city.cpp:50:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   50 |    if(ok) vis2[Cp]=1; cnt++;
      |                       ^~~

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