Submission #444640

#	Time	Username	Problem	Language	Result	Execution time	Memory
444640		ivan_tudor	Capital City (JOI20_capital_city)	C++14	0 / 100	524 ms	41344 KiB

capital_city

#include<bits/stdc++.h>
using namespace std;
const int N = 200005;
int sz[N];
bool wasC[N];
vector<int> gr[N];
int par[N];
int inc[N];
vector<int> col[N];
bool usedc[N];
int cl[N];
void dfs_prec(int nod, int dad, int val){
  sz[nod] = 1;

  par[nod] = dad;
  inc[nod] = val;
  usedc[cl[nod]] = false;

  for(auto x:gr[nod]){
    if(x!=dad && wasC[x] == false){
      dfs_prec(x, nod, val);
      sz[nod]+=sz[x];
    }
  }
}
int find_centro(int nod, int dad, int n){
  for(auto x:gr[nod]){
    if(x!=dad && wasC[x] == false && sz[x] > n/2)
      return find_centro(x, nod, n);
  }
  return nod;
}
int ans = N;
int k;
void centr_deco(int nod, int &cnt){
  dfs_prec(nod, 0, ++cnt);
  int C = find_centro(nod, 0, sz[nod]);
  queue<int> q;
  bool ok = true;
  for(auto x:col[cl[C]]){
    if(inc[x] != cnt){
      ok = false;
      break;
    }
    q.push(x);
  }
  usedc[cl[C]] = true;
  int cans = 1;
  while(q.size() && ok){
    int nod = q.front();
    q.pop();
    int colour = cl[par[nod]];
    if(colour != 0 && usedc[colour] == false){
      for(auto x:col[colour]){
        if(inc[x] != cnt){
          ok = false;
          break;
        }
        q.push(x);
      }
      usedc[colour] = true;
      cans++;
    }
  }
  if(ok == true){
    ans = min(ans, cans - 1);
  }
  wasC[C] = true;
  for(auto x:gr[C]){
    if(wasC[x] == false){
      centr_deco(x, cnt);
    }
  }
}
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n;
  cin>>n>>k;
  for(int i =1 ; i <n; i++){
    int a, b;
    cin>>a>>b;
    gr[a].push_back(b);
    gr[b].push_back(a);
  }
  for(int i = 1; i <=n; i++){
    cin>>cl[i];
    col[cl[i]].push_back(i);
  }
  int aux = 0;
  centr_deco(1, aux);
  cout<<ans;
  return 0;
}

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