Submission #220203

#	Time	Username	Problem	Language	Result	Execution time	Memory
220203		fedoseevtimofey	Capital City (JOI20_capital_city)	C++14	11 / 100	3105 ms	524288 KiB

capital_city

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>

using namespace std;

typedef long long ll;

const int N = 2e5 + 7;
const int M = 4e6 + 7;

vector <int> g[N];
int col[N];

bool used[N];

int dfs(int u, int size, int &c, int p = -1) {
  int sum = 1;
  for (auto v : g[u]) {
    if (!used[v] && v != p) {
      sum += dfs(v, size, c, u);
    }
  }
  if (c == -1 && (2 * sum >= size || p == -1)) {
    c = u;
  }
  return sum;
}

int uk;

vector <int> gr[M];
vector <int> rg[M];

int num[N];
vector <int> who[N];

void add(int u, int v) {
  gr[u].push_back(v);
  rg[v].push_back(u);
}


vector <int> subtr;

void solve(int u, int p = -1) {
  subtr.push_back(u);
  for (auto v : g[u]) {
    if (!used[v] && v != p) {
      num[v] = uk++;
      add(num[v], col[v]);
      add(num[v], num[u]);
      solve(v, u);
    }
  }
}

int timer = 0;
int cur_cnt[N];
int last_seen[N];

void build(int u, int size, int last) {
  int c = -1; 
  dfs(u, size, c);
  used[c] = true;
  num[c] = uk++;
  add(num[c], col[c]);
  vector <vector <int>> cmp;
  for (auto v : g[c]) {
    if (!used[v]) {
      num[v] = uk++;
      add(num[v], col[v]);
      add(num[v], num[c]);

      subtr.clear();
      solve(v, c);
      cmp.push_back(subtr);
    }
  }
  cmp.push_back({c});
  for (auto sb : cmp) {
    ++timer;
    for (auto v : sb) {
      who[col[v]].push_back(v);
      if (last_seen[col[v]] != timer) {
        last_seen[col[v]] = timer;
        ++cur_cnt[col[v]];
      }
    }
  }

  for (auto sb : cmp) {
    for (auto v : sb) {
      if (cur_cnt[col[v]] > 1) {
        for (auto vr : who[col[v]]) {
          add(col[v], num[vr]);
        }
      }
      who[col[v]] = {};
      cur_cnt[col[v]] = 0;
    }
  }

  cmp = {};
   
  for (auto v : g[c]) {
    if (!used[v]) {
      build(v, (size + 1) / 2, c);
    }
  }
}


vector <int> t;
int cmp[M];
int sz[M];
bool hv[M];

void get_topsort(int u) {
  used[u] = true;
  for (auto v : gr[u]) {
    if (!used[v]) {
      get_topsort(v);
    }
  }
  t.push_back(u);
}

int cnt = 0;

int k;

void jhfs(int u) {
  used[u] = true;
  cmp[u] = cnt;
  if (u < k) ++sz[cnt];
  for (auto v : rg[u]) {
    if (!used[v]) {
      jhfs(v);
    }
  }
}

int ans;

void zhfs(int u) {
  used[u] = true;
  for (auto v : rg[u]) {
    if (!used[v]) {
      zhfs(v);
    }
    cmp[u] |= cmp[v];
  }
  if (!cmp[u] && sz[u] > 0) {
    ans = min(ans, sz[u]);
  }
  if (sz[u] > 0) cmp[u] = 1;
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n;
  cin >> n >> k;
  for (int i = 0; i + 1 < n; ++i) {
    int u, v;
    cin >> u >> v;
    --u, --v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 0; i < n; ++i) {
    cin >> col[i];
    --col[i];
  }

  uk = k;
  build(0, n, -1);
  
 
  fill(used, used + uk, false);
  for (int i = 0; i < uk; ++i) {
    if (!used[i]) {
      get_topsort(i);
    }
  }
  reverse(t.begin(), t.end());
  fill(used, used + uk, false);   
  for (int u : t) {
    if (!used[u]) {
      jhfs(u);
      ++cnt;
    }
  }
  for (int i = 0; i < uk; ++i) rg[i] = {};
  for (int i = 0; i < uk; ++i) {
    for (auto v : gr[i]) {
      if (cmp[i] != cmp[v]) {
        rg[cmp[i]].push_back(cmp[v]);
      }
    }
  }
  for (int i = 0; i < cnt; ++i) {
    sort(rg[i].begin(), rg[i].end());
    rg[i].resize(unique(rg[i].begin(), rg[i].end()) - rg[i].begin());
  }
  ans = n;
  fill(used, used + cnt, 0);
  for (int i = 0; i < cnt; ++i) cmp[i] = 0;
  for (int i = 0; i < cnt; ++i) {
    if (!used[i]) {
      zhfs(i);
    }
  }
  cout << ans - 1 << '\n';
}

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