제출 #750360

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
750360		Dan4Life	수도 (JOI20_capital_city)	C++17	100 / 100	2575 ms	35380 KiB

capital_city

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

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

int getSub(int s, int par){
	sub[s] = 1; p[s]=par;
	for(auto u : adj[s])
		if(u!=par 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 par, bool ok){
	p[s] = ok?par:-1;
	if(ok) vis2[C[s]]=0;
	for(auto u : adj[s])
		if(u!=par and !vis[u]) dfs(u,s,ok);
}

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

컴파일 시 표준 에러 (stderr) 메시지

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

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