結果

問題 No.1166 NADA DNA
ユーザー SHIJOU
提出日時 2020-08-29 19:14:41
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 159 ms / 3,000 ms
コード長 2,459 bytes
コンパイル時間 2,708 ms
コンパイル使用メモリ 201,472 KB
最終ジャッジ日時 2025-01-13 20:32:39
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 0xccccccc;
const ll LINF = 922337203685477580LL;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

struct UnionFind {
  vector<int> par; // 親を指すvector,-par[親]は木のサイズ
  UnionFind(int n):par(n, -1) {} // uniteで親を埋め込んでいく必要あり
  int root(int x) { // 親をたどる&データの整理
    if(par[x] < 0) return x;
    return par[x] = root(par[x]);
  }
  bool unite(int x, int y) { // データの結合
    x = root(x);
    y = root(y);
    if(x == y) return false;
    if(par[x] > par[y]) swap(x, y);
    par[x] += par[y];
    par[y] = x;
    return true;
  }
  bool same(int x, int y) {return root(x) == root(y);} // 所属判定
  int size(int x) {return -par[root(x)];} // 木のサイズ
};

struct edge {
  int u, v;
  int64_t cost;
  edge(int u=0, int v=0, int64_t cost=0):u(u), v(v), cost(cost) {} 
};

bool comp(const edge& e1, const edge& e2) {
  return e1.cost < e2.cost;
}

// 辺の数でresize & 入力
vector<edge> es;
//最小全域木, Vは頂点数
int64_t kruskal(int V) {
  int E = es.size();
  sort(es.begin(), es.end(), comp);
  UnionFind uft(V);
  int64_t res = 0;
  for(int i = 0; i < E; ++i) {
    edge e = es[i];
    if(!uft.same(e.u, e.v)) {
      uft.unite(e.u, e.v);
      res += e.cost;
    }
  }
  return res;
}

#define N 1010

//head

int n, l;
string g[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> l;
  rep(i, n) cin >> g[i];
  rep(i, n) rep(j, i) {
    int cnt = 0;
    rep(k, l) if(g[i][k] != g[j][k]) cnt++;
    es.emplace_back(i, j, cnt);
  }
  cout << kruskal(n) << endl;
}
0