Submission #1058978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058978		zNatsumi	Cities (BOI16_cities)	C++17	0 / 100	57 ms	18004 KiB

cities

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define ii pair<int, int>
#define iii pair<int, ii>
#define fi first
#define se second
#define all(x) x.begin(), x.end()

const int N = 2e5 + 5,
          INF = 1e9,
          mod = 1e9 + 7;
// code

int n, m, k, id[N], sz[N], st, res = 0;
bool mrk[N];
vector<ii> ad[N];
iii edge[N];

int fset(int i){ return i == id[i] ? i : id[i] = fset(id[i]); }
bool uset(int a, int b){
  a = fset(a), b = fset(b);
  if(a == b) return false;
  if(sz[a] < sz[b]) swap(a, b);
  id[b] = a;
  sz[a] += sz[b];
  return true;
}

bool dfs(int u, int p){
  bool chk = false;
  for(auto x : ad[u]){
    int v, c; tie(v, c) = x;
    if(v == p) continue;

    bool ok = dfs(v, u);
    if(ok) res += c;
    chk |= ok;
  }
  return mrk[u] | chk;
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }

  cin >> n >> k >> m;
  for(int i = 1; i <= k; i++){
    int a; cin >> a;
    mrk[a] = true; st = a;
  }
  for(int i = 1; i <= m; i++){
    int a, b, c; cin >> a >> b >> c;
    edge[i] = {c, {a, b}};
  }

  sort(edge+1, edge+m+1);
  for(int i = 1; i <= n; i++) id[i] = i, sz[i] = 1;

  for(int i = 1; i <= m; i++){
    int u = edge[i].se.fi, v = edge[i].se.se, c = edge[i].fi;

    if(uset(u, v)){
//      cerr << u << " " << v << " " << c << endl;
      ad[u].push_back({v, c});
      ad[v].push_back({u, c});
    }
  }
  dfs(st, 0);
  cout << res << endl;

  return 0;
}

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