Submission #414359

#TimeUsernameProblemLanguageResultExecution timeMemory
414359ritul_kr_singhCapital City (JOI20_capital_city)C++17
100 / 100
605 ms35792 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define sp << ' ' << #define nl << '\n' const int MAXN = 2e5; int n, k, color[MAXN], par[MAXN], s[MAXN], ans = MAXN, curr; vector<int> g[MAXN], h[MAXN]; bitset<MAXN> r, vis, bad; void calcSize(int u){ s[u] = 1; for(int v : g[u]) if(!s[v]) calcSize(v), s[u] += s[v]; } int find(int u, int p, int sz){ bool f = 1; while(f){ f = 0; s[p] -= s[u], s[u] = sz; for(int v : g[u]){ if(!r[v] && s[v] > sz/2){ p = u, u = v; f = 1; break; } } } return u; } void dfs(int u){ vis[color[u]] = 0; for(int v : g[u]) if(s[v] < s[u] && !r[v]) dfs(v), par[v] = curr * MAXN + u; } void decompose(int c){ r[c = curr = find(c, c, s[c])] = 1; par[c] = curr * MAXN + c; dfs(c); int res = 0; vis[color[c]] = 1; vector<int> st; for(int i : h[color[c]]){ if(res == MAXN) break; if(par[i] / MAXN != c) res = MAXN; else st.push_back(i); } while(!st.empty() && res < MAXN){ int u = st.back(); st.pop_back(); int p = par[u] % MAXN; if(!vis[color[p]]){ if(bad[color[p]]){ res = MAXN; break; } ++res; for(int v : h[color[p]]){ if(par[v] / MAXN == c && res < MAXN) st.push_back(v); else res = MAXN; } if(res < MAXN) vis[color[p]] = 1; else bad[color[p]] = 1; } } ans = min(ans, res); bad[color[c]] = 1; for(int v : g[c]) if(!r[v]) decompose(v); } signed main(){ cin.tie(0)->sync_with_stdio(0); int x, y; cin >> n >> k; for(int i=1; i<n; ++i){ cin >> x >> y; --x, --y; g[x].push_back(y); g[y].push_back(x); } for(int i=0; i<n; ++i){ cin >> color[i]; --color[i]; h[color[i]].push_back(i); } calcSize(0); decompose(0); cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...