Submission #537431

#	Time	Username	Problem	Language	Result	Execution time	Memory
537431		8e7	Capital City (JOI20_capital_city)	C++17	11 / 100	3080 ms	32880 KiB

capital_city

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 300005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
vector<int> adj[maxn];
int c[maxn], dep[maxn], f[maxn];
pii ran[maxn];
int pa[maxn];
void dfs(int n, int par, int d) {
	pa[n] = par;
	dep[n] = d;
	for (int v:adj[n]) {
		if (v != par) {
			dfs(v, n, d+1);
		}
	}
}
vector<int> pos[maxn];
bool vis[maxn], mark[maxn];
int prv[maxn];
int main() {
	io
	int n, K;
	cin >> n >> K;
	for (int i = 0;i < n - 1;i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);	
	}
	
	for (int i = 1;i <= n;i++) {
		cin >> c[i];
		pos[c[i]].push_back(i);
	}
	int ans = n - 1;	
	for (int i = 1;i <= K;i++) {
		for (int j = 1;j <= n;j++) vis[j] = mark[j] = 0;
		queue<int> que;
		dfs(pos[i][0], 0, 0);
		vis[pos[i][0]] = 1;
		for (int j:pos[i]) que.push(j);
		mark[i] = 1;
		int cnt = 0;
		while (que.size()) {
			int cur = que.front();que.pop();
			if (vis[cur]) continue;
			while (!vis[cur]) {
				vis[cur] = 1;
				if (!mark[c[cur]]) {
					cnt++;
					mark[c[cur]] = 1;
					for (int v:pos[c[cur]]) que.push(v);
				}
				cur = pa[cur];
			}
		}
		ans = min(ans, cnt);
	}
	cout << ans << endl;
}

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