Submission #932925

#TimeUsernameProblemLanguageResultExecution timeMemory
932925ParsaSCapital City (JOI20_capital_city)C++17
41 / 100
1533 ms524288 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 = 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++; 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...