Submission #19546475


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

template <class A, class B> bool cmin(A& a, B b) { return a > b && (a = b, true); }
template <class A, class B> bool cmax(A& a, B b) { return a < b && (a = b, true); }

class UnionFind {
private:
  int sz;
  vector<int> par, size_;
public:
  UnionFind() {}
  UnionFind(int n) : sz(n), par(sz), size_(sz, 1) {
    iota(par.begin(), par.end(), 0);
  }
  int root(int x) {
    if (par.at(x) == x) return x;
    else return par.at(x) = root(par.at(x));
  }
  void unit(int x,int y) {
    x = root(x), y = root(y);
    if (x == y) return;
    if (size_.at(x) < size_.at(y)) swap(x, y);
    par.at(y) = x;
    size_.at(x) += size_.at(y);
  }
  int size(int x) {
    x = root(x);
    return size_.at(x);
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
};

template<typename T> class Kruskal {
public:
  struct edge {
    int u, v;
    T cost;
    bool operator < (const edge& another) const {
      return cost < another.cost;
    }
  };
  vector<edge> es;
  int V;
  Kruskal(int n) : V(n) {}
  void add(int u, int v, T cost) {
    es.push_back((edge) {u, v, cost});
  }
  T solve() {
    UnionFind UF(V);
    T res = 0;
    int cnt = 0;
    sort(es.begin(),es.end());
    for (edge &e : es) {
      if (!UF.same(e.u, e.v)) {
        UF.unit(e.u, e.v);
        res += e.cost;
        cnt++;
        if (cnt == V - 1) break;
      }
    }
    return res;
  }
};

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int N, M;
  cin >> N >> M;
  vector<tuple<int, int, int>> V(N);
  for (int i = 0; i < N; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    V.at(i) = {a, b, c};
  }
  vector<tuple<int, int, int>> V2(M);
  for (int i = 0; i < M; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    V2.at(i) = {a, b, c};
  }
  
  double mi = DBL_MAX;
  for (int bit = 0; bit < 1 << M; bit++) {
    int MX = N + __builtin_popcount(bit);
    auto V3 = V;
    for (int i = 0; i < M; i++) {
      if (bit >> i & 1) V3.push_back(V2.at(i));
    }
    Kruskal<double> K(MX);
    for (int i = 0; i < MX; i++) {
      for (int j = 0; j < i; j++) {
        auto [a, b, c] = V3.at(i);
        auto [d, e, f] = V3.at(j);
        if (c == f) K.add(i, j, hypot(a - d, b - e));
        else K.add(i, j, hypot(a - d, b - e) * 10);
      }
    }
    cmin(mi, K.solve());
  }
  cout << fixed << setprecision(6) << mi << '\n';
}

Submission Info

Submission Time
Task L - Gradation
User ninoi
Language C++ (GCC 9.2.1)
Score 6
Code Size 2479 Byte
Status AC
Exec Time 8 ms
Memory 3872 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 6 / 6
Status
AC × 2
AC × 31
Set Name Test Cases
Sample example_01.txt, example_02.txt
All example_01.txt, example_02.txt, subtask_01_01.txt, subtask_01_02.txt, subtask_01_03.txt, subtask_01_04.txt, subtask_01_05.txt, subtask_01_06.txt, subtask_01_07.txt, subtask_01_08.txt, subtask_01_09.txt, subtask_01_10.txt, subtask_01_11.txt, subtask_01_12.txt, subtask_01_13.txt, subtask_01_14.txt, subtask_01_15.txt, subtask_01_16.txt, subtask_01_17.txt, subtask_01_18.txt, subtask_01_19.txt, subtask_01_20.txt, subtask_01_21.txt, subtask_01_22.txt, subtask_01_23.txt, subtask_01_24.txt, subtask_01_25.txt, subtask_01_26.txt, subtask_01_27.txt, subtask_01_28.txt, subtask_01_29.txt
Case Name Status Exec Time Memory
example_01.txt AC 5 ms 3692 KB
example_02.txt AC 3 ms 3744 KB
subtask_01_01.txt AC 3 ms 3640 KB
subtask_01_02.txt AC 2 ms 3712 KB
subtask_01_03.txt AC 2 ms 3788 KB
subtask_01_04.txt AC 3 ms 3828 KB
subtask_01_05.txt AC 3 ms 3752 KB
subtask_01_06.txt AC 3 ms 3696 KB
subtask_01_07.txt AC 7 ms 3872 KB
subtask_01_08.txt AC 5 ms 3772 KB
subtask_01_09.txt AC 6 ms 3720 KB
subtask_01_10.txt AC 3 ms 3808 KB
subtask_01_11.txt AC 6 ms 3860 KB
subtask_01_12.txt AC 4 ms 3784 KB
subtask_01_13.txt AC 2 ms 3756 KB
subtask_01_14.txt AC 8 ms 3664 KB
subtask_01_15.txt AC 5 ms 3724 KB
subtask_01_16.txt AC 3 ms 3724 KB
subtask_01_17.txt AC 4 ms 3740 KB
subtask_01_18.txt AC 5 ms 3728 KB
subtask_01_19.txt AC 2 ms 3804 KB
subtask_01_20.txt AC 5 ms 3660 KB
subtask_01_21.txt AC 5 ms 3840 KB
subtask_01_22.txt AC 2 ms 3688 KB
subtask_01_23.txt AC 4 ms 3780 KB
subtask_01_24.txt AC 6 ms 3728 KB
subtask_01_25.txt AC 5 ms 3824 KB
subtask_01_26.txt AC 4 ms 3732 KB
subtask_01_27.txt AC 4 ms 3788 KB
subtask_01_28.txt AC 5 ms 3724 KB
subtask_01_29.txt AC 5 ms 3836 KB