제출 #899039

#제출 시각아이디문제언어결과실행 시간메모리
899039danikoynov수도 (JOI20_capital_city)C++14
0 / 100
275 ms39596 KiB
/** ____ ____ ____ ____ ____ ____ ||l |||e |||i |||n |||a |||d || ||__|||__|||__|||__|||__|||__|| |/__\|/__\|/__\|/__\|/__\|/__\| **/ #include<bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } const int maxn = 2e5 + 10; int n, k, c[maxn]; vector < int > adj[maxn]; vector < int > col[maxn]; void input() { cin >> n >> k; for (int i = 1; i < n; i ++) { int v, u; cin >> v >> u; ///cout << "edge " << v << " " << u << endl; adj[v].push_back(u); adj[u].push_back(v); } for (int i = 1; i <= n; i ++) cin >> c[i], col[c[i]].push_back(i); } int sub[maxn], par[maxn], last[maxn], used[maxn]; int timer; void calc(int v, int p) { //cout << "calc " << v << " " << p << endl; last[v] = timer; par[v] = p; sub[v] = 1; for (int u : adj[v]) { //cout << "neib " << v << " " << u << endl; if (used[u] || u == p) continue; calc(u, v); sub[v] += sub[u]; } } int find_centroid(int v, int p, int sz) { for (int u : adj[v]) { if (u == p || used[u]) continue; if (sub[u] >= sz / 2) return find_centroid(u, v, sz); } return v; } int ans, mark[maxn]; void make_tree(int v) { /**cout << "make tree" << endl; for (int i = 1; i <= n; i ++) cout << last[i] << " "; cout << endl;*/ vector < int > cs; /**for (int i = 1; i <= k; i ++) mark[i] = 0;*/ queue < int > q; for (int cur : col[c[v]]) { if (last[cur] != timer) return; q.push(cur); } mark[c[v]] = 1; cs.push_back(c[v]); int cnt = 0; while(!q.empty()) { int cur = q.front(); q.pop(); ///cout << "queue " << cur << endl; if (par[cur] != -1 && !mark[c[par[cur]]]) { cnt ++; mark[c[par[cur]]] = 1; cs.push_back(c[par[cur]]); for (int ver : col[c[par[cur]]]) { if (last[ver] != timer) { for (int ps : cs) mark[ps] = 0; return; } q.push(ver); } } } ///cout << cnt << endl; ans = min(ans, cnt); for (int ps : cs) mark[ps] = 0; ///exit(0); } void decompose(int v) { timer ++; calc(v, -1); int centroid = find_centroid(v, -1, sub[v]); ///cout << "centroid " << v << endl; make_tree(centroid); used[centroid] = 1; for (int u : adj[centroid]) { if (!used[u]) decompose(u); } } void solve() { input(); ans = n; decompose(1); cout << ans << endl; } int main() { speed(); 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...