oj.uz

Submission #251967

# Submission time Handle Problem Language Result Execution time Memory
251967 2020-07-23T09:53:23 Z uacoder123 Capital City (JOI20_capital_city) C++14
0 / 100
 3000 ms 47172 KB 
#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],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)
{
  par[node]=p;
  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]];
    }
  }
}
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(vis1[cit[tc[node]][i]]!=vis1[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++;
        ans=min(solve(cen),ans);
        m.clear();
        m1.clear();
      }
    }
    memset(vis1,0,sizeof(vis1));
  }
  cout<<ans<<endl;
  return 0;
}

Compilation message

capital_city.cpp: In function 'void dfs(int, int, int)':
capital_city.cpp:26: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:37: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:51:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<cit[tc[node]].size();++i)
                 ~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10624 KB Output is correct
2 Correct 8 ms 10496 KB Output is correct
3 Correct 6 ms 10496 KB Output is correct
4 Incorrect 6 ms 10496 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10624 KB Output is correct
2 Correct 8 ms 10496 KB Output is correct
3 Correct 6 ms 10496 KB Output is correct
4 Incorrect 6 ms 10496 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3096 ms 47172 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10624 KB Output is correct
2 Correct 8 ms 10496 KB Output is correct
3 Correct 6 ms 10496 KB Output is correct
4 Incorrect 6 ms 10496 KB Output isn't correct
5 Halted 0 ms 0 KB -