Submission #428202

#TimeUsernameProblemLanguageResultExecution timeMemory
428202juggernautCapital City (JOI20_capital_city)C++17
11 / 100
3062 ms92580 KiB
#include<bits/stdc++.h> #define fr first #define sc second using namespace std; void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);} typedef long long ll; #define USING_ORDERED_SET 0 #if USING_ORDERED_SET #include<bits/extc++.h> using namespace __gnu_pbds; template<class T>using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; #endif template<class T>void umax(T &a,T b){if(a<b)a=b;} template<class T>void umin(T &a,T b){if(b<a)a=b;} #ifdef IOI2021SG #define printl(args...)printf(args) #else #define printl(args...)((void)0) #endif int n,k; int tin[200005],tout[200005],timer,up[200005][18]; vector<int>g[200005],color[200005],g1[200005],g2[200005]; int a[200005]; void dfs(int v,int p){ tin[v]=++timer; up[v][0]=p; for(int i=1;i<18;i++)up[v][i]=up[up[v][i-1]][i-1]; for(int to:g[v])if(to!=p)dfs(to,v); tout[v]=++timer; } bool upper(int a,int b){ return tin[a]<=tin[b]&&tout[a]>=tout[b]; } int lca(int a,int b){ if(upper(a,b))return a; if(upper(b,a))return b; for(int i=17;i>=0;i--)if(!upper(up[a][i],b))a=up[a][i]; return up[a][0]; } int lca(vector<int>&vec){ int l=vec[0]; for(int i=1;i<(int)vec.size();i++)l=lca(l,vec[i]); return l; } unordered_map<int,bool>vs[200005]; vector<pair<int,int>>edges; void add_edge(int a,int b){ if(a^b){ if(vs[a][b])return; vs[a][b]=true; edges.emplace_back(a,b); g1[a].push_back(b); } } void add(int v,int a,int l){ while(a!=l){ a=up[a][0]; add_edge(v,::a[a]); if(v^::a[a])break; } } int cnt=0; bool vis[200005]; int low[200005],_up[200005],tt,last; int sz[200005]; stack<int>ss; int id[200005]; bool used[200005]; void run(int u,int p=-1){ low[u]=_up[u]=tt++; used[u]=1; ss.push(u); for(auto x:g1[u]) if(used[x] && !id[x])umin(low[u],_up[x]); else if(!id[x]) run(x,u),umin(low[u],low[x]); if(low[u] == _up[u]){ int cur; ++last; do{ cur = ss.top(); ss.pop(); id[cur] = last; sz[last]++; }while(cur != u); } } int dp[200005]; int goo(int v){ if(~dp[v])return dp[v]; dp[v]=sz[v]; for(int to:g2[v])dp[v]+=goo(to); return dp[v]; } int main(){ memset(dp,-1,sizeof dp); scanf("%d%d",&n,&k); for(int i=1;i<n;i++){ int x,y; scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); } for(int i=1;i<=n;i++){ scanf("%d",&a[i]); color[a[i]].push_back(i); } dfs(1,1); for(int i=1;i<=k;i++){ int l=lca(color[i]); for(int j=0;j<(int)color[i].size();j++)add(i,color[i][j],l); } for(int i=1;i<=k;i++)if(!used[i])run(i); for(auto to:edges)if(id[to.fr]^id[to.sc]){ g2[id[to.fr]].push_back(id[to.sc]); } int ans=k; for(int i=1;i<=last;i++)umin(ans,goo(i)); printf("%d",ans-1); }

Compilation message (stderr)

capital_city.cpp: In function 'void usaco(std::string)':
capital_city.cpp:5:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp:5:66: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | void usaco(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
      |                                                           ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
capital_city.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~
capital_city.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...