oj.uz

Submission #1058978

# Submission time Handle Problem Language Result Execution time Memory
1058978 2024-08-14T15:35:01 Z zNatsumi Cities (BOI16_cities) C++17
0 / 100
 57 ms 18004 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8628 KB Output is correct
3 Incorrect 1 ms 8540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 18004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 17792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 18004 KB Output isn't correct
2 Halted 0 ms 0 KB -