Submission #931605

#TimeUsernameProblemLanguageResultExecution timeMemory
931605vjudge1Capital City (JOI20_capital_city)C++17
11 / 100
223 ms6100 KiB
#include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "debug.h" #else #define debug(...) 0 #endif typedef long long ll; const int N = 2e3 + 4; int n, k, c[N], cnt[N]; bool have[N], seen[N]; vector<int> T[N], D[N]; void dfs1(int v, int p) { have[c[v]] = 1; for (int u : T[v]) { if (u != p) { dfs1(u, v); } } } void dfs2(int v) { seen[v] = 1; for (int u : D[v]) { if (seen[u] == 0) { dfs2(u); } } } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> k; for (int i = 1; i < n; i++) { int v, u; cin >> v >> u; v--; u--; T[v].push_back(u); T[u].push_back(v); } for (int i = 0; i < n; i++) { cin >> c[i]; c[i]--; } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cnt[j] = have[j] = 0; } for (int v : T[i]) { dfs1(v, i); for (int j = 0; j < n; j++) { cnt[j] += have[j]; have[j] = 0; } } for (int j = 0; j < k; j++) { if (cnt[j] >= 2) { D[j].push_back(c[i]); } } } int ans = k; for (int i = 0; i < k; i++) { for (int j = 0; j < k; j++) { seen[j] = 0; } dfs2(i); int cand = 0; for (int j = 0; j < k; j++) { cand += seen[j]; } ans = min(ans, cand); } cout << ans - 1; 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...