oj.uz

답안 #750348

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
750348 2023-05-29T12:12:12 Z Dan4Life 수도 (JOI20_capital_city) C++17
0 / 100
 171 ms 34736 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 171 ms 34736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 9684 KB Output isn't correct
2 Halted 0 ms 0 KB -