Submission #887263

#	Time	Username	Problem	Language	Result	Execution time	Memory
887263		vjudge1	Cities (BOI16_cities)	C++17	0 / 100	888 ms	262144 KiB

cities

#include <bits/stdc++.h>
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define fast_io ios::sync_with_stdio(false);cin.tie(0);
#define what(x) cerr << #x << " is " << x << '\n';
#define kill(x) {cout << x << '\n'; return 0;}
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define pb push_back
#define ll long long
#define F first
#define S second
const ll inf = 1e18, mod = 1e9 + 7, delta = 1e9 + 9, SQ = 450, P = 6065621;
 
using namespace std;

#define int ll

const ll N = 1e5 + 10, LG = 22;
int parr[N], sz[N], par[N][LG], h[N];
vector<pair<int, pii>> edges;
unordered_set<int> sack[N];
vector<int> vec, del[N];
vector<pii> adj[N];
ll ans;

int root (int v) {
  if (parr[v] == v) return v;
  return parr[v] == root(parr[v]);
}

bool mrg (int v, int u) {
  v = root(v), u = root(u);
  if (u == v) return false;
  if (sz[u] > sz[v]) swap(u, v);
  sz[v] += sz[u];
  parr[u] = v;
  return true;
}

void dfs (int v, int p = -1) {
  par[v][0] = p;
  if (p + 1) h[v] = h[p] + 1;
  for (int i = 1; i < LG; i++) 
    if (par[v][i - 1] + 1)
      par[v][i] = par[par[v][i - 1]][i - 1];
  for (auto u: adj[v])
    if (u.F - p) dfs(u.F, v);
}

int lca (int v, int u) {
  if (u == v) return v;
  if (h[u] < h[v]) swap(u, v);
  for (int i = LG - 1; i >= 0; i--)
    if (par[u][i] + 1 && h[v] <= h[par[u][i]])
      u = par[u][i];
  if (u == v) return v;
  for (int i = LG - 1; i >= 0; i--)
    if (par[v][i] - par[u][i])
      v = par[v][i], u = par[u][i];
  return par[v][0];
}

void diefes (int v, int p = -1) {
  for (auto u: adj[v])
    if (u.F - p) {
      diefes(u.F, v);
      if (sack[u.F].size()) {
        ans += u.S;
      }
      if (sack[u.F].size() > sack[v].size()) {
        sack[v].swap(sack[u.F]);
      }
      for (auto x: sack[u.F]) {
        sack[v].insert(x);
      }
      sack[u.F].clear();
    }
  for (auto u: del[v])
    if (sack[v].count(u))
      sack[v].erase(u);
}

int32_t main() {
  fast_io;
  int n, k, m;
  cin >> n >> k >> m;
  fill(sz, sz + N, 1);
  iota(parr, parr + N, 0);
  memset(par, -1, sizeof par);
  for (int i = 1; i <= k; i++) {
    int x;
    cin >> x;
    vec.pb(x);
  }
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    edges.pb({w, {u, v}});
  }
  sort(all(edges));
  for (auto e: edges) {
    if (mrg(e.S.F, e.S.S)) {
      adj[e.S.F].pb({e.S.S, e.F});
      adj[e.S.S].pb({e.S.F, e.F});
    }
  }
  dfs(1);
  int l = lca(vec[0], vec[1]);
  for (int i = 2; i < k; i++)
    l = lca(l, vec[i]);
  for (auto u: vec) 
    sack[u].insert(1);
  del[l].pb(1);
  diefes(1);
  cout << ans << '\n';
  return 0;
}

• Subtask 1: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26