Submission #251975

#	Time	Username	Problem	Language	Result	Execution time	Memory
251975		uacoder123	Capital City (JOI20_capital_city)	C++14	11 / 100	3060 ms	36984 KiB

capital_city

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define mp(i,a) make_pair(i,a)
#define pb(a) push_back(a)
#define bit(x,b) (x&(1LL<<b))
 
typedef long long int lli;
typedef pair <lli,lli> ii;
typedef pair <lli,ii> iii;
typedef vector <lli> vi;
int vis[200001],vis1[200001],vis2[200001],par[200001],sz[200001],n,c;
vi cit[200001],al[200001];
int tc[200001];
unordered_map<int,int> m,m1;
void dfs(int node,int p,int no)
{
  vis1[node]=no;
  sz[node]=1;
  for(int i=0;i<al[node].size();++i)
  {
    if(vis[al[node][i]]+vis1[al[node][i]]==0)
    {
      dfs(al[node][i],node,no);
      sz[node]+=sz[al[node][i]];
    }
  }
}
void dfs2(int node,int p,int no)
{
  vis2[node]=no;
  par[node]=p;
  for(int i=0;i<al[node].size();++i)
  {
    if(vis[al[node][i]]+vis2[al[node][i]]==0)
      dfs2(al[node][i],node,no);
  }
}
int tell(int node,int p,int to)
{
  for(int i=0;i<al[node].size();++i)
    if(al[node][i]!=p&&vis[al[node][i]]==0&&sz[al[node][i]]>to/2)
      return(tell(al[node][i],node,to));
  return(node);
}
int ins(int node)
{
  if(m.find(node)!=m.end())
    return(0);
  m[node]=1;
  int r=0;
  if(m1.find(tc[node])==m1.end())
  {
    m1[tc[node]]=1;
    for(int i=0;i<cit[tc[node]].size();++i)
    {
      if(vis2[cit[tc[node]][i]]!=vis2[node])
        return(-1);
      r=min(ins(cit[tc[node]][i]),r);
    }
  }
  if(m.find(par[node])==m.end())
    r=min(ins(par[node]),r);
  return(r);
}
int solve(int node)
{
  int co=ins(node);
  if(co==-1)
    return(c-1);
  return(m1.size()-1);
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin>>n>>c;
  for(int i=0;i<n-1;++i)
  {
    int f,s;
    cin>>f>>s;
    al[f].pb(s);
    al[s].pb(f);
  }
  for(int i=0;i<n;++i)
  {
    int f;
    cin>>f;
    tc[i+1]=f;
    cit[f].pb(i+1);
  }
  int co=0,ans=c-1,no=1;
  while(co!=n)
  {
    for(int i=1;i<=n;++i)
    {
      if(vis[i]+vis1[i]==0)
      {
        dfs(i,i,no);
        no++;
        int cen=tell(i,i,sz[i]);
        vis[cen]=1;
        co++;
        dfs2(cen,cen,no);
        no++;
        ans=min(solve(cen),ans);
        m.clear();
        m1.clear();
      }
    }
    memset(vis1,0,sizeof(vis1));
    memset(vis2,0,sizeof(vis2));
  }
  cout<<ans<<endl;
  return 0;
}

Compilation message (stderr)

capital_city.cpp: In function 'void dfs(int, int, int)':
capital_city.cpp:25:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<al[node].size();++i)
               ~^~~~~~~~~~~~~~~~
capital_city.cpp: In function 'void dfs2(int, int, int)':
capital_city.cpp:38:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<al[node].size();++i)
               ~^~~~~~~~~~~~~~~~
capital_city.cpp: In function 'int tell(int, int, int)':
capital_city.cpp:46:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<al[node].size();++i)
               ~^~~~~~~~~~~~~~~~
capital_city.cpp: In function 'int ins(int)':
capital_city.cpp:60:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<cit[tc[node]].size();++i)
                 ~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 59