oj.uz

Submission #1036766

# Submission time Handle Problem Language Result Execution time Memory
1036766 2024-07-27T16:36:36 Z juicy Capital City (JOI20_capital_city) C++17
0 / 100
 2757 ms 524288 KB 
#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 = 3400005;

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][u] = ++m;
        g[m].push_back(id[i - 1][u]);
        g[m].push_back(id[i - 1][pr[i - 1][u]]);
      }
      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]) {
        assert(lab[i] > lab[j]);
        graph[lab[i]].push_back(lab[j]);
      }
    }
  }
  int res = MAX;
  for (int i = 1; i <= scc; ++i) {
    for (int j : graph[i]) {
      cnt[i] += cnt[j];
    }
    if (cnt[i]) {
      res = min(res, cnt[i]);
    }
  }
  cout << res - 1;
  return 0;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 164944 KB Output is correct
2 Correct 64 ms 164860 KB Output is correct
3 Correct 63 ms 164948 KB Output is correct
4 Incorrect 62 ms 164900 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 164944 KB Output is correct
2 Correct 64 ms 164860 KB Output is correct
3 Correct 63 ms 164948 KB Output is correct
4 Incorrect 62 ms 164900 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 2757 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 164944 KB Output is correct
2 Correct 64 ms 164860 KB Output is correct
3 Correct 63 ms 164948 KB Output is correct
4 Incorrect 62 ms 164900 KB Output isn't correct
5 Halted 0 ms 0 KB -