Submission #930394

#TimeUsernameProblemLanguageResultExecution timeMemory
930394ParsaSCapital City (JOI20_capital_city)C++17
0 / 100
73 ms26116 KiB
// 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 = 2e5 + 5, lg = 20; int n, k, a[N]; vector<int> adj[N], vec[N]; int up[N][lg], tin[N], tout[N], T, h[N]; int f[N], par[N]; void dfs(int v, int p) { up[v][0] = p; par[v] = 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> V; int out[N]; void dfs2(int v, int p) { vector<int> dat; while (!V.empty() && h[f[V.back()]] >= h[f[v]]) { dat.pb(V.back()); V.pop_back(); } V.pb(v); int l = -1, r = V.size() - 1; while (r - l > 1) { int mid = (l + r) >> 1; if (h[V[mid]] >= h[f[v]]) r = mid; else l = mid; } if (a[v] != a[V[r]]) { out[a[v]]++; } for (auto u : adj[v]) { if (u != p) dfs2(u, v); } V.pop_back(); while (!dat.empty()) { V.pb(dat.back()); dat.pop_back(); } } bool vis[N]; int col[N]; 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 >> a[i]; vec[a[i]].pb(i); } if (n > 20) return; dfs(1, 1); for (int i = 1; i <= k; i++) { int u = vec[i].back(); for (auto v : vec[i]) { u = lca(u, v); } for (auto v : vec[i]) f[v] = u; } dfs2(1, 0); for (int v = 1; v <= n; v++) { int u = par[v], mx = v; while (u != f[v] && v != f[v]) { if (h[f[u]] < h[f[mx]]) { mx = u; } u = par[u]; } u = mx; if (a[v] != a[u]) { out[a[v]]++; } } vector<pair<int, int> > ver; for (int i = 1; i <= k; i++) { if (out[i] == 0) { ver.pb(mp(h[f[vec[i].back()]], f[vec[i].back()])); } } sort(ver.begin(), ver.end(), greater<pair<int, int> >()); int ans = 1e9; for (auto [x, v] : ver) { queue<int> q; q.push(a[v]); if (col[a[v]]) continue; col[a[v]] = a[v]; bool ok = true; int cnt = 0; while (!q.empty()) { int c = q.front(); q.pop(); if (col[c] != a[v]) { ok = false; break; } for (auto w : vec[c]) { if (w == v) continue; int u = par[w]; if (col[a[u]] == 0) { col[a[u]] = a[v]; cnt++; q.push(a[u]); } else if (col[a[u]] != a[v]) ok = false; } } if (ok) ans = min(ans, cnt); } cout << ans << '\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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...