Submission #1036775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036775		juicy	Capital City (JOI20_capital_city)	C++17	11 / 100	1066 ms	524288 KiB

capital_city

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5, LG = 18, MAX = 3600005;

int n, k, m;
int lst[N], c[N], dep[N], pr[LG][N], id[LG][N], low[MAX], num[MAX], cnt[MAX], lab[MAX];
vector<int> tree[N], g[MAX], graph[MAX];

void dfs(int u) {
  for (int v : tree[u]) {
    if (v != pr[0][u]) {
      pr[0][v] = u;
      id[0][v] = c[u];
      for (int i = 1; i < LG; ++i) {
        id[i][v] = ++m;
        pr[i][v] = pr[i - 1][pr[i - 1][v]];
        g[m].push_back(id[i - 1][v]);
        g[m].push_back(id[i - 1][pr[i - 1][v]]);
      }
      dep[v] = dep[u] + 1;
      dfs(v);
    }
  }
}

int lca(int u, int v) {
  if (dep[u] < dep[v]) {
    swap(u, v);
  }
  for (int j = LG - 1; ~j; --j) {
    if (dep[u] - (1 << j) >= dep[v]) {
      u = pr[j][u];
    }
  }
  if (u == v) {
    return u;
  }
  for (int j = LG - 1; ~j; --j) {
    if (pr[j][u] != pr[j][v]) {
      u = pr[j][u], v = pr[j][v];
    }
  }
  return pr[0][u];
}

void add(int u, int p) {
  int col = c[u];
  for (int i = LG - 1; ~i; --i) {
    if (dep[u] - (1 << i) >= dep[p]) {
      g[col].push_back(id[i][u]);
      u = pr[i][u];
    }
  }
}

vector<int> st;
int timer, scc;

void DFS(int u) {
  st.push_back(u);
  low[u] = num[u] = ++timer;
  for (int v : g[u]) {
    if (!num[v]) {
      DFS(v);
      low[u] = min(low[u], low[v]);
    } else {
      low[u] = min(low[u], num[v]);
    }
  }
  if (low[u] == num[u]) {
    ++scc;
    while (1) {
      int v = st.back(); st.pop_back();
      num[v] = MAX;
      lab[v] = scc;
      if (v == u) {
        break;
      }
    }
  } 
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> k; m = k;
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    tree[u].push_back(v);
    tree[v].push_back(u);
  }  
  for (int i = 1; i <= n; ++i) {
    cin >> c[i];
  }
  dfs(1);
  for (int i = 1; i <= n; ++i) {
    if (lst[c[i]]) {
      int x = lca(i, lst[c[i]]);
      add(i, x);
      add(lst[c[i]], x);
    }
    lst[c[i]] = i;
  }
  for (int i = 1; i <= m; ++i) {
    if (!num[i]) {
      DFS(i);
    }
  }
  for (int i = 1; i <= k; ++i) {
    ++cnt[lab[i]];
  }
  for (int i = 1; i <= m; ++i) {
    for (int j : g[i]) {
      if (lab[i] != lab[j]) {
        graph[lab[i]].push_back(lab[j]);
      }
    }
  }
  int res = MAX;
  for (int i = 1; i <= scc; ++i) {
    bool out = 0;
    for (int j : graph[i]) {
      if (cnt[j]) {
        out = 1;
        cnt[i] = 1;
      }
    }
    if (!out && cnt[i]) {
      res = min(res, cnt[i]);
    }
  }
  cout << res - 1;
  return 0;
}

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