oj.uz

Submission #444640

# Submission time Handle Problem Language Result Execution time Memory
444640 2021-07-14T13:34:24 Z ivan_tudor Capital City (JOI20_capital_city) C++14
0 / 100
 524 ms 41344 KB 
#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.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 524 ms 41344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

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