Submission #1001768

#TimeUsernameProblemLanguageResultExecution timeMemory
1001768UnforgettableplCapital City (JOI20_capital_city)C++17
11 / 100
622 ms52228 KiB
#include <bits/stdc++.h> using namespace std; #define int long long void strat1(int n){ int k; cin >> k; vector<vector<int>> adj(n+1); for(int i=1;i<n;i++){ int a,b;cin>>a>>b; adj[a].emplace_back(b); adj[b].emplace_back(a); } vector<int> col(n+1); for(int i=1;i<=n;i++)cin>>col[i]; vector<int> nodes(k+1); function<void(int,int,int)> dfs = [&](int x,int par,int dep){ nodes[col[x]] = x; for(int&i:adj[x])if(i!=par)dfs(i,x,dep+1); }; dfs(1,0,1); vector<vector<int>> compoadj(k+1); for(int i=1;i<=k;i++){ set<int> bad; function<bool(int,int)> pdfs = [&](int x,int p){ bool found = col[x]==i; for(int&i:adj[x])if(i!=p)if(pdfs(i,x))found=true; if(found)bad.insert(col[x]); return found; }; pdfs(nodes[i],0); for(int x:bad)compoadj[i].emplace_back(x); } vector<bool> visited(k+1); int siz = 0; function<void(int)> compodfs = [&](int x){ if(visited[x])return; siz++; visited[x]=true; for(int&i:compoadj[x])compodfs(i); }; int ans = n; for(int i=1;i<=k;i++){ siz = 0; visited = vector<bool>(k+1); compodfs(i); ans = min(ans,siz-1); } cout << ans << '\n'; } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; if(n<=2000){ strat1(n); return 0; } int k; cin >> k; vector<vector<int>> adj(n+1); for(int i=1;i<n;i++){ int a,b;cin>>a>>b; adj[a].emplace_back(b); adj[b].emplace_back(a); } vector<int> colcor(n+1); vector<int> col(n+1); for(int i=1;i<=n;i++)cin>>colcor[i]; function<void(int,int,int)> dfs = [&](int x,int par,int idx){ col[idx] = colcor[x]; for(int&i:adj[x])if(i!=par)dfs(i,x,idx+1); }; for(int i=1;i<=n;i++)if(adj[i].size()==1){ dfs(i,0,1); break; } vector<int> minidx(k+1); vector<int> maxidx(k+1); for(int i=1;i<=n;i++)maxidx[col[i]]=i; for(int i=n;i;i--)minidx[col[i]]=i; vector<vector<int>> compoadj(k+1); vector<vector<int>> comporevadj(k+1); for(int i=1;i<=k;i++){ for(int x=minidx[i];x<=maxidx[i];x++){ if(col[x]!=i){ compoadj[i].emplace_back(col[x]); comporevadj[col[x]].emplace_back(i); x = maxidx[col[x]]; } } } vector<bool> visited(k+1); vector<int> order; vector<int> siz(k+1); vector<int> mycompo(k+1); function<void(int)> topo = [&](int x){ if(visited[x])return; visited[x]=true; for(int&i:compoadj[x])topo(i); order.emplace_back(x); }; for(int i=1;i<=k;i++)if(!visited[i])topo(i); reverse(order.begin(),order.end()); function<void(int,int)> cr_dfs = [&](int x,int compo){ if(mycompo[x]){ if(mycompo[x]!=compo)siz[mycompo[x]]=n+1; return; } siz[compo]++; mycompo[x] = compo; for(int&i:comporevadj[x])cr_dfs(i,compo); }; int components = 0; int ans = n+1; for(int i=0;i<k;i++)if(mycompo[order[i]]==0)cr_dfs(order[i],++components); for(int i=1;i<=components;i++){ ans = min(ans,siz[components]-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...