test/aoj/GRL_2_A.kruskal.test.cpp

• View this file on GitHub
• Last update: 2024-09-20 12:04:43+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_A

Depends on

• Union-Find (src/DataStructure/UnionFind.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_A
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <algorithm>
#include <numeric>
#include "src/DataStructure/UnionFind.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N, M;
 cin >> N >> M;
 UnionFind uf(N);
 int s[M], t[M];
 long long w[M];
 for (int i= 0; i < M; i++) cin >> s[i] >> t[i] >> w[i];
 long long ans= 0;
 int ord[M];
 iota(ord, ord + M, 0), sort(ord, ord + M, [&](int l, int r) { return w[l] < w[r]; });
 for (int i: ord)
  if (uf.unite(s[i], t[i])) ans+= w[i];
 cout << ans << '\n';
 return 0;
}

#line 1 "test/aoj/GRL_2_A.kruskal.test.cpp"
// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/2/GRL_2_A
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <algorithm>
#include <numeric>
#line 2 "src/DataStructure/UnionFind.hpp"
#include <vector>
#line 4 "src/DataStructure/UnionFind.hpp"
class UnionFind {
 std::vector<int> par;
public:
 UnionFind(int n): par(n, -1) {}
 int leader(int u) { return par[u] < 0 ? u : par[u]= leader(par[u]); }
 bool unite(int u, int v) {
  if ((u= leader(u)) == (v= leader(v))) return false;
  if (par[u] > par[v]) std::swap(u, v);
  return par[u]+= par[v], par[v]= u, true;
 }
 bool connected(int u, int v) { return leader(u) == leader(v); }
 int size(int u) { return -par[leader(u)]; }
};
#line 8 "test/aoj/GRL_2_A.kruskal.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(false);
 int N, M;
 cin >> N >> M;
 UnionFind uf(N);
 int s[M], t[M];
 long long w[M];
 for (int i= 0; i < M; i++) cin >> s[i] >> t[i] >> w[i];
 long long ans= 0;
 int ord[M];
 iota(ord, ord + M, 0), sort(ord, ord + M, [&](int l, int r) { return w[l] < w[r]; });
 for (int i: ord)
  if (uf.unite(s[i], t[i])) ans+= w[i];
 cout << ans << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	00_sample1.in	AC	5 ms	4 MB
g++-13	00_sample2.in	AC	5 ms	4 MB
g++-13	critical1.in	AC	5 ms	4 MB
g++-13	critical2.in	AC	6 ms	4 MB
g++-13	critical3.in	AC	19 ms	6 MB
g++-13	out1.in	AC	4 ms	4 MB
g++-13	out10.in	AC	26 ms	6 MB
g++-13	out11.in	AC	11 ms	4 MB
g++-13	out12.in	AC	16 ms	5 MB
g++-13	out13.in	AC	13 ms	5 MB
g++-13	out14.in	AC	15 ms	5 MB
g++-13	out15.in	AC	11 ms	4 MB
g++-13	out2.in	AC	4 ms	3 MB
g++-13	out3.in	AC	4 ms	4 MB
g++-13	out4.in	AC	4 ms	4 MB
g++-13	out5.in	AC	4 ms	3 MB
g++-13	out6.in	AC	26 ms	6 MB
g++-13	out7.in	AC	27 ms	6 MB
g++-13	out8.in	AC	26 ms	6 MB
g++-13	out9.in	AC	26 ms	6 MB
clang++-18	00_sample1.in	AC	5 ms	4 MB
clang++-18	00_sample2.in	AC	4 ms	4 MB
clang++-18	critical1.in	AC	5 ms	4 MB
clang++-18	critical2.in	AC	6 ms	4 MB
clang++-18	critical3.in	AC	19 ms	6 MB
clang++-18	out1.in	AC	5 ms	4 MB
clang++-18	out10.in	AC	27 ms	6 MB
clang++-18	out11.in	AC	11 ms	4 MB
clang++-18	out12.in	AC	16 ms	5 MB
clang++-18	out13.in	AC	13 ms	4 MB
clang++-18	out14.in	AC	15 ms	5 MB
clang++-18	out15.in	AC	11 ms	4 MB
clang++-18	out2.in	AC	4 ms	4 MB
clang++-18	out3.in	AC	4 ms	4 MB
clang++-18	out4.in	AC	4 ms	4 MB
clang++-18	out5.in	AC	4 ms	4 MB
clang++-18	out6.in	AC	27 ms	6 MB
clang++-18	out7.in	AC	27 ms	6 MB
clang++-18	out8.in	AC	27 ms	6 MB
clang++-18	out9.in	AC	27 ms	6 MB

Back to top page