Submission #681852

#	Time	Username	Problem	Language	Result	Execution time	Memory
681852		peijar	Capital City (JOI20_capital_city)	C++17	100 / 100	511 ms	105144 KiB

capital_city

#include <bits/stdc++.h>
#define int long long
using namespace std;

string to_string(string s) { return s; }
template <typename T> string to_string(T v) {
  bool first = true;
  string res = "[";
  for (const auto &x : v) {
    if (!first)
      res += ", ";
    first = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}

void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
  cout << ' ' << to_string(H);
  dbg_out(T...);
}

#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

signed main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  int nbSommets, nbVilles;
  cin >> nbSommets >> nbVilles;

  vector<vector<int>> adj(nbSommets);
  for (int i = 1; i < nbSommets; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }

  vector<int> ville(nbSommets), inVille(nbVilles);
  for (int i = 0; i < nbSommets; ++i) {
    cin >> ville[i];
    --ville[i];
    inVille[ville[i]]++;
  }

  vector<set<int>> adjVille(nbVilles), radjVille(nbVilles);

  auto Solve = [&](auto solve, int u, int p) -> map<int, int> {
    map<int, int> cnt;
    cnt[ville[u]]++;
    for (int v : adj[u])
      if (v != p) {
        auto cntV = solve(solve, v, u);
        if (cntV[ville[v]] < inVille[ville[v]] and ville[u] != ville[v]) {
          adjVille[ville[v]].insert(ville[u]);
          radjVille[ville[u]].insert(ville[v]);
          dbg(ville[v], ville[u]);
        }
        if (cnt.size() < cntV.size())
          cnt.swap(cntV);
        for (auto [x, y] : cntV)
          cnt[x] += y;
      }
    return cnt;
  };

  Solve(Solve, 0, 0);

  vector<bool> seen(nbVilles);
  vector<int> order;

  auto Dfs1 = [&](auto dfs, int u) {
    if (seen[u])
      return;
    seen[u] = true;
    for (int v : adjVille[u])
      dfs(dfs, v);
    order.push_back(u);
  };
  for (int i = 0; i < nbVilles; ++i)
    Dfs1(Dfs1, i);

  reverse(order.begin(), order.end());
  vector<int> id(nbVilles);
  seen.assign(nbVilles, false);
  int nbSCC = 0;
  auto Dfs2 = [&](auto dfs, int u) {
    if (seen[u])
      return;
    seen[u] = true;
    id[u] = nbSCC;
    for (int v : radjVille[u])
      dfs(dfs, v);
  };
  for (int i : order)
    if (!seen[i]) {
      Dfs2(Dfs2, i);
      nbSCC++;
    }

  vector<bool> isGood(nbSCC, true);
  vector<int> sz(nbSCC);
  for (int i = 0; i < nbVilles; ++i) {
    sz[id[i]]++;
    for (int j : adjVille[i])
      if (id[j] != id[i])
        isGood[id[i]] = false;
  }
  dbg(id);

  int sol = 1e18;
  for (int i = 0; i < nbSCC; ++i)
    if (isGood[i])
      sol = min(sol, sz[i]);
  cout << sol - 1 << endl;
}

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