Submission #1219550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219550		siewjh	Capital City (JOI20_capital_city)	C++20	100 / 100	426 ms	35372 KiB

capital_city

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int inf = 1e9 + 7;
vector<int> adj[MAXN], tcl[MAXN];
int ca[MAXN], p[MAXN], sz[MAXN], lvl[MAXN];
bool ins[MAXN], vis[MAXN], city[MAXN];
int ans = inf;
int dfs(int x, int par){
	ins[x] = 1;
	int ssz = 1;
	for (int nn : adj[x]){
		if (nn == par || lvl[nn] != -1) continue;
		ssz += dfs(nn, x);
	}
	return sz[x] = ssz;
}
int dfs2(int x, int par, int ssz){
	for (int nn : adj[x]){
		if (nn == par || lvl[nn] != -1) continue;
		if (sz[nn] > ssz / 2) return dfs2(nn, x, ssz);
	}
	return x;
}
void dfs3(int x, int par){
	p[x] = par;
	for (int nn : adj[x]){
		if (nn == par || lvl[nn] != -1) continue;
		dfs3(nn, x);
	}
}
int calc(int cent){
	queue<int> q; vis[cent] = 1; q.push(cent);
	int res = 0;
	while (!q.empty()){
		int cn = q.front(), cc = ca[cn]; q.pop();
		if (!city[cc]){
			city[cc] = 1; res++;
			for (int nn : tcl[cc]){
				if (!ins[nn]) return inf;
				if (vis[nn]) continue;
				vis[nn] = 1; q.push(nn);
			}
		}
		int par = p[cn];
		if (par != -1 && !vis[par]){
			vis[par] = 1; q.push(par);
		}
	}
	return res;
}
void dfs4(int x, int par){
	ins[x] = 0; vis[x] = 0; city[ca[x]] = 0;
	for (int nn : adj[x]){
		if (nn == par || lvl[nn] != -1) continue;
		dfs4(nn, x);
	}
}
void decomp(int x, int clvl){
	int ssz = dfs(x, -1), cent = dfs2(x, -1, ssz);
	lvl[cent] = clvl;
	dfs3(cent, -1);
	ans = min(ans, calc(cent));
	dfs4(cent, -1);
	for (int nn : adj[cent]){
		if (lvl[nn] != -1) continue;
		decomp(nn, clvl + 1);
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int nums, cnum; cin >> nums >> cnum;
	for (int i = 1; i < nums; i++){
		int a, b; cin >> a >> b;
		adj[a].push_back(b); adj[b].push_back(a);
	}
	for (int i = 1; i <= nums; i++){
		int c; cin >> c;
		ca[i] = c; tcl[c].push_back(i);
	}
	memset(lvl, -1, sizeof(lvl));
	decomp(1, 0);
	cout << ans - 1;
}

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