Submission #993210

#TimeUsernameProblemLanguageResultExecution timeMemory
993210prvocisloCapital City (JOI20_capital_city)C++17
100 / 100
458 ms62684 KiB
// meow cat, please meow back =^_^= #include <algorithm> #include <bitset> #include <cassert> #include <chrono> #include <cmath> #include <deque> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <random> #include <set> #include <string> #include <vector> typedef long long ll; typedef long double ld; using namespace std; int n, k; const int logn = 18; const int maxn = 200005; vector<int> adj[maxn], adj_rev[maxn]; bool used[maxn], in[maxn]; vector<int> order, component; void dfs1(int v) { used[v] = true; for (auto u : adj[v]) if (!used[u]) dfs1(u); order.push_back(v); } void dfs2(int v) { used[v] = true; component.push_back(v); for (auto u : adj_rev[v]) if (!used[u]) dfs2(u); } void add(int u, int v) { adj[u].push_back(v); adj_rev[v].push_back(u); } int solve() { fill(used, used + k, false); for (int i = 0; i < k; i++) if (!used[i]) dfs1(i); fill(used, used + k, false); reverse(order.begin(), order.end()); int ans = k; for (auto v : order) if (!used[v]) { dfs2(v); bool okay = true; for (int i : component) in[i] = true; for (int i : component) { for (int j : adj[i]) if (!in[j]) okay = false; } for (int i : component) in[i] = false; if (okay) ans = min(ans, (int)component.size() - 1); component.clear(); } return ans; } vector<vector<int> > g, l, col; vector<int> d, c; void dfs(int u) { for (int j = 1; j < logn; j++) l[j][u] = l[j - 1][l[j - 1][u]]; for (int v : g[u]) if (v != l[0][u]) d[v] = d[u] + 1, l[0][v] = u, dfs(v); } int lca(int u, int v) { if (d[u] < d[v]) swap(u, v); for (int i = logn - 1; i >= 0; i--) if (d[l[i][u]] >= d[v]) u = l[i][u]; for (int i = logn - 1; i >= 0; i--) if (l[i][u] != l[i][v]) u = l[i][u], v = l[i][v]; return u == v ? u : l[0][u]; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> k; g.assign(n, {}), l.assign(logn, vector<int>(n, 0)), d.assign(n, 0), col.assign(k, {}), c.assign(n, -1); for (int i = 0, a, b; i < n - 1; i++) cin >> a >> b, g[--a].push_back(--b), g[b].push_back(a); for (int i = 0; i < n; i++) { cin >> c[i]; col[--c[i]].push_back(i); } dfs(0); for (int i = 0; i < k; i++) { int lc = col[i][0]; for (int j : col[i]) lc = lca(lc, j); for (int j : col[i]) if (j != lc) { add(i, c[l[0][j]]); } } cout << solve() << "\n"; 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...