Submission #428135

#TimeUsernameProblemLanguageResultExecution timeMemory
428135juggernautCapital City (JOI20_capital_city)C++17
11 / 100
3082 ms315064 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]; } 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); g2[b].push_back(a); } } void add(int v,int a,int b){ int lca=::lca(a,b); while(a!=lca){ a=up[a][0]; add_edge(v,::a[a]); } while(b!=lca){ b=up[b][0]; add_edge(v,::a[b]); } } int cnt=0; bool vis[200005]; void run(int v){ vis[v]=true; cnt++; for(int to:g1[v])if(!vis[to])run(to); } int main(){ 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++) for(int j=1;j<(int)color[i].size();j++)add(i,color[i][0],color[i][j]); int ans=k; for(int i=1;i<=k;i++){ for(int j=1;j<=k;j++)vis[j]=false; cnt=0; run(i); umin(ans,cnt); } 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:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
capital_city.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         scanf("%d%d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~
capital_city.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         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...