Submission #1235388

#TimeUsernameProblemLanguageResultExecution timeMemory
1235388poatCapital City (JOI20_capital_city)C++17
0 / 100
0 ms328 KiB
// #pragma GCC optimize("Ofast") // #pragma GCC target("popcnt") #include <bits/stdc++.h> using namespace std; #define int long long // #define double long double #define mkp make_pair #define txt freopen("shortcut.in", "r", stdin), freopen("shortcut.out", "w", stdout); const int N = 1000, K = 50, inf = 1e14, mod = 1e9 + 7; const double eps = 1e-6; vector<int> gr[N]; int Col[N]; vector<int> C[N]; bool blocked[N]; int CntCol[N]; bool vis[N]; bool usCol[N]; int cnt[N]; bool used[N]; int P[N]; void dfs(int x, int par) { P[x] = par; cnt[x] = 1; for(auto i : gr[x]) { if(i == par || used[i]) continue; dfs(i, x); cnt[x] += cnt[i]; } } int find(int x, int par, int m) { bool res = (cnt[x] >= ((m + 1) / 2)); for(auto i : gr[x]) { if(i == par || used[i]) continue; res = min(res, (cnt[i] <= ((m + 1) / 2))); int k = find(i, x, m); if(k != -1) return k; } if(res) return x; return -1; } vector<int> vec; void kol(int x, int par) { vec.push_back(x); for(auto i : gr[x]) { if(i == par || used[i]) continue; kol(i, x); } } int solve(int x) { if(vec.size() == 1) return (C[Col[x]].size() == 1 ? 0 : 1e9); int cent = find(x, 0, vec.size()); dfs(cent, 0); used[cent] = 1; // getchar(); // cout << x << ' ' << cent << '\n'; // cout << x << ' ' << cent << '\n'; // for(auto i : vec) // cout << cnt[i] << ' '; // cout << "\n"; // for(auto i : vec) // cout << P[i] << ' '; // exit(0); for(auto i : vec) CntCol[Col[i]]++; for(auto i : vec) { if(CntCol[Col[i]] != C[Col[i]].size()) blocked[Col[i]] = 1; } // getchar(); // cout << x << ' ' << cent << '\n'; // for(auto i : vec) // cout << i << ' '; // cout << '\n'; // for(auto i : vec) // { // if(blocked[Col[i]]) // cout << i << ' '; // } // cout << "\n\n"; bool fl = 0; int res = 0; vis[0] = 1; if(!blocked[Col[x]]) { fl = 1; queue<int> Q; for(auto i : C[Col[x]]) Q.push(i); usCol[Col[x]] = 1; while(!Q.empty()) { int y = Q.front(); // cout << y << ' '; Q.pop(); while(!vis[y]) { // cout << y << ' '; vis[y] = 1; if(blocked[Col[y]]) { fl = 0; break; } if(!usCol[Col[y]]) { usCol[Col[y]] = 1; res++; for(auto i : C[Col[y]]) Q.push(i); } y = P[y]; } if(!fl) break; } } if(!fl) res = 1e9; for(auto i : vec) usCol[Col[i]] = vis[i] = CntCol[i] = 0; for(auto i : gr[cent]) { if(used[i]) continue; vec.clear(); kol(i, cent); // solve(i); res = min(res, solve(i)); } return res; } void solve() { int n, k; cin >> n >> k; for(int i = n - 1, a, b; i--;) { cin >> a >> b; gr[a].push_back(b); gr[b].push_back(a); } for(int i = 1; i <= n; i++) { cin >> Col[i]; C[Col[i]].push_back(i); vec.push_back(i); } dfs(1, 0); int ans = solve(1); assert(ans < n); cout << ans << '\n'; } signed main() { // txt; // ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); int T = 1; for(; T--; solve()); } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...