Submission #897905

#	Time	Username	Problem	Language	Result	Execution time	Memory
897905		NeroZein	Capital City (JOI20_capital_city)	C++17	0 / 100	374 ms	85632 KiB

capital_city

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define deb(...)
#endif

const int LOG = 18;
const int N = 2e5 + 5;

int dep[N];
int root[N];
int color[N];
int up[LOG][N];
int p[N], sz[N];
int p2[N], sz2[N];
vector<int> g[N];
set<int> conn[N];
set<int> times[N];
int ord, in[N], out[N];
bool ineed[N], needme[N];

void dfs(int v, int pr) {
  in[v] = ord++;
  for (int u : g[v]) {
    if (u == pr) continue; 
    dep[u] = dep[v] + 1; 
    up[0][u] = v;
    for (int j = 1; j < LOG; ++j) {
      up[j][u] = up[j - 1][up[j - 1][u]];
    }
    dfs(u, v); 
  }
  out[v] = ord - 1; 
}

int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  for (int j = 0; j < LOG; ++j) {
    if ((dep[u] - dep[v]) >> j & 1) {
      u = up[j][u];
    }
  }
  if (u == v) return v;
  for (int j = LOG - 1; j >= 0; --j) {
    if (up[j][u] != up[j][v]) {
      u = up[j][u], v = up[j][v];
    }
  }
  return up[0][v];
}

int get(int v) {
  return p[v] = (p[v] == v ? v : get(p[v])); 
}

int get2(int v) {
  return p2[v] = (p2[v] == v ? v : get2(p2[v])); 
}

void unite(int v, int u) {
  v = get(v), u = get(u); 
  if (sz[v] < sz[u]) swap(u, v); 
  p[u] = v;
  sz[v] += sz[u];
  root[v] = lca(root[v], root[u]); 
  for (int w : times[u]) {
    times[v].insert(w);
  }
}

void unite2(int v, int u) {
  v = get2(v); u = get2(u);
  if (sz2[v] < sz2[u]) swap(u, v);
  p2[u] = v;
  sz2[v] += sz2[u];
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, k;
  cin >> n >> k;
  for(int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1, 1);
  iota(p + 1, p + 1 + k, 1); 
  fill(sz + 1, sz + 1 + n, 1);
  for (int i = 1; i <= n; ++i) {
    cin >> color[i];
    times[color[i]].insert(in[i]);
    p2[i] = i;
    sz2[i] = 1; 
    if (root[color[i]] == 0) {
      root[color[i]] = i;
    } else {
      root[color[i]] = lca(root[color[i]], i); 
    }
  }
  for (int v = 1; v <= n; ++v) {
    for (int u : g[v]) {
      int pv = get(color[v]), pu = get(color[u]);
      if (pv == pu) {//same color
        unite2(u, v); 
        continue; 
      }
      if (u == up[0][v]) {
        if (root[pv] != v) {
          ineed[pu] = true;
        }
        continue; 
      }
      auto it = times[pv].lower_bound(in[u]);
      if (it != times[pv].end() && *it <= out[u]) {
        ineed[pu] = true; 
      }
      if (root[pu] != u) {
        needme[pu] = true; 
      }
    }
    for (int u : g[v]) {
      int pv = get(color[v]), pu = get(color[u]);
      if (pv == pu) continue; //same color
      if (ineed[pu] && needme[pu]) {
        unite(pv, pu);
        unite2(v, u); 
      }
      ineed[pu] = needme[pu] = false;
    }
  }
  int ans = k;
  for (int i = 1; i <= n; ++i) {
    conn[color[i]].insert(get2(i)); 
  }
  for (int i = 1; i <= k; ++i) {
    if (conn[i].size() == 1) {
      ans = min(ans, sz[get(i)]); 
    }
  }
  cout << ans - 1 << '\n';
  return 0;
}

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