Submission #932924

#	Time	Username	Problem	Language	Result	Execution time	Memory
932924		ParsaS	Capital City (JOI20_capital_city)	C++17	31 / 100	230 ms	96840 KiB

capital_city

// In the name of God
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 4e5 + 5, lg = 20;
int n, k;
int up[N][lg], f[N], c[N];
vector<int> adj[N], ver[N];
int h[N], tin[N], tout[N], T;
int par[N];

void dfs(int v, int p) {
	par[v] = p;
	up[v][0] = p;
	for (int i = 1; i < lg; i++)
		up[v][i] = up[up[v][i - 1]][i - 1];
	tin[v] = ++T;
	for (auto u : adj[v]) {
		if (u != p) {
			h[u] = h[v] + 1;
			dfs(u, v);
		}
	}
	tout[v] = T;
}

bool anc(int v, int u) {
	return tin[v] <= tin[u] && tout[v] >= tout[u];
}
int lca(int v, int u) {
	if (tin[v] > tin[u]) swap(v, u);
	if (anc(v, u)) return v;
	for (int i = lg - 1; i >= 0; i--)
		if (!anc(up[u][i], v))
			u = up[u][i];
	return up[u][0];

}
vector<int> out[N], in[N];
int CNT = 0;

void dfs2(int v, int p) {
	int u = par[v];
	while (h[u] > h[f[c[v]]]) {
		out[c[v]].pb(c[u]);
		in[c[u]].pb(c[v]);

		CNT++;
		assert(CNT <= n * 3);
		u = par[u];
	}
	par[v] = u;
	if (h[u] >= h[f[c[v]]]) {
		out[c[v]].pb(c[f[c[v]]]);
		in[c[f[c[v]]]].pb(c[v]);


		par[v] = par[f[c[v]]];
	}
	for (auto u : adj[v]) {
		if (u != p)
			dfs2(u, v);
	}
}
bool vis[N];
int col[N];
vector<int> vec;

void dfs3(int v) {
	vis[v] = true;
	for (auto u : out[v]) {
		if (!vis[u]) dfs3(u);
	}
	vec.pb(v);
}
vector<int> V;

void dfs4(int v, int x) {
	col[v] = x;
	for (auto u : in[v]) {
		if (!col[u])
			dfs4(u, x);
	}
	V.pb(v);
}

void solve() {
	cin >> n >> k;
	for (int i = 0; i < n - 1; i++) {
		int v, u; cin >> v >> u;
		adj[v].pb(u);
		adj[u].pb(v);
	}
	for (int i = 1; i <= n; i++) cin >> c[i], ver[c[i]].pb(i);

	dfs(1, 0);
	h[0] = -1;
	tout[0] = T;

	for (int i = 1; i <= k; i++) {
		f[i] = ver[i].back();
		for (auto v : ver[i])
			f[i] = lca(f[i], v);
	}

	dfs2(1, 0);
	for (int i = 1; i <= k; i++) {
		if (!vis[i])
			dfs3(i);
	}
	int ans = n + 1;
	for (int i = k - 1; i >= 0; i--) {
		int w = vec[i];
		if (col[w] == 0) {
			V.clear();
			dfs4(w, w);
			bool ok = true;
			int cnt = V.size();
			for (auto v : V) {
				for (auto u : out[v])
					ok &= col[u] == col[v];
			}
			if (ok) ans = min(ans, cnt);	
		}
	}
	cout << ans - 1 << '\n';

}

int32_t main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int tc = 1; // cin >> tc;
	while (tc--) {
		solve();
	}

	return 0;
}

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