Submission #750322

#TimeUsernameProblemLanguageResultExecution timeMemory
750322Dan4LifeCapital City (JOI20_capital_city)C++17
0 / 100
311 ms37652 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define all(a) begin(a),end(a) const int mxN = (int)2e5+2; vector<int> v[mxN]; int n, m, ans = mxN; int col[mxN], sub[mxN], par[mxN], vis[mxN], vis2[mxN]; vector<int> adj[mxN]; int getSub(int s, int p){ sub[s] = 1; par[s]=p; for(auto u : adj[s]) if(u!=p and !vis[u]) sub[s]+=getSub(u,s); return sub[s]; } int findCen(int s, int p, int n){ for(auto u : adj[s]) if(u!=p and !vis[u] and sub[u]>n/2) return findCen(u,s,n); return s; } void dfs(int s, int p){ par[s] = p; for(auto u : adj[s]) if(u!=p and !vis[u]) dfs(u,s); } void cenDec(int cen, int p){ cen = findCen(cen,p,getSub(cen,cen)); if(!vis2[col[cen]]){ queue<int> Q = queue<int>(); Q.push(cen); bool ok = 1; int cnt = 0; while(!Q.empty() and ok){ auto a = Q.front(); Q.pop(); int C = col[par[a]]; if(vis[a]) ok=0; else if(!vis2[C]){ for(auto u : v[C]) Q.push(u); vis2[C]=1; cnt++; } } if(ok) ans = min(ans, cnt); } vis[cen] = 1; for(auto u : adj[cen]) if(u!=p and !vis[u]) cenDec(u,cen); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for(int i = 1; i < n; i++){ int a, b; cin >> a >> b; adj[a].pb(b), adj[b].pb(a); } for(int i = 1; i <= n; i++) cin >> col[i], v[col[i]].pb(i); cenDec(1,-1); cout << ans << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...