제출 #945166

#제출 시각아이디문제언어결과실행 시간메모리
945166ArashJafariyan수도 (JOI20_capital_city)C++17
11 / 100
3057 ms75544 KiB
#include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "debug.h" #else #define debug(...) 0 #endif #define pb push_back #define i2 array<int, 2> #define ll long long const int N = 2e5 + 4; int n, k, c[N], sz[N], root[N], par[N]; bool done[N], in[N]; vector<int> adj[N], V[N]; queue<int> q; void fill_sz(int v,int p = 0) { in[c[v]] = 0; par[v] = p; root[v] = (p == 0 ? v : root[p]); for (int u : adj[v]) { if (u != p && !done[u]) { fill_sz(u, v); sz[v] += sz[u]; } } } int find_cen(int v, int siz, int p = 0) { for (int u : adj[v]) { if (!done[u] && u != p && sz[u] > siz / 2) { return find_cen(u, siz, v); } } return v; } int dfs(int v = 1) { fill_sz(v); v = find_cen(v, sz[v]); done[v] = true; q.push(c[v]); vector<int> save; int ans = 0; while (q.size()) { int col = q.front(); q.pop(); if (in[col] == 1) { continue; } in[col] = 1; for (int u : V[col]) { if (root[u] != v) { ans = k; break; } if (par[u] != 0) { if (!in[c[par[u]]]) { q.push(c[par[u]]); } } } save.pb(col); ans++; } for (int u : adj[v]) { if (!done[u]) { ans = min(ans, dfs(u)); } } return ans; } void solve() { cin >> n >> k; for (int i = 1; i < n; 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]; V[c[i]].pb(i); } cout << dfs() - 1; } int main() { ios::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; while (t--) { 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...