結果
問題 |
No.3087 University Coloring
|
ユーザー |
![]() |
提出日時 | 2025-04-04 21:32:29 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 88 ms / 2,000 ms |
コード長 | 2,685 bytes |
コンパイル時間 | 4,432 ms |
コンパイル使用メモリ | 121,312 KB |
実行使用メモリ | 6,528 KB |
最終ジャッジ日時 | 2025-04-04 21:35:44 |
合計ジャッジ時間 | 5,500 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <iostream> #include <iomanip> #include <cassert> #include <vector> #include <algorithm> #include <utility> #include <numeric> // #include "Src/Utility/BinarySearch.hpp" // #include "Src/Sequence/CompressedSequence.hpp" // #include "Src/Sequence/RunLengthEncoding.hpp" #include <cstdint> #include <cstddef> namespace zawa { using i16 = std::int16_t; using i32 = std::int32_t; using i64 = std::int64_t; using i128 = __int128_t; using u8 = std::uint8_t; using u16 = std::uint16_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using usize = std::size_t; } // namespace zawa namespace zawa { class DisjointSetUnion { public: DisjointSetUnion() = default; DisjointSetUnion(usize n) : n_{n}, comps_{n}, data_(n, -1) { data_.shrink_to_fit(); } u32 leader(u32 v) { return data_[v] < 0 ? v : static_cast<u32>(data_[v] = leader(data_[v])); } bool same(u32 u, u32 v) { return leader(u) == leader(v); } bool merge(u32 u, u32 v) { assert(u < n_); assert(v < n_); u = leader(u); v = leader(v); if (u == v) return false; comps_--; if (data_[u] > data_[v]) std::swap(u, v); data_[u] += data_[v]; data_[v] = u; return true; } inline usize size() const noexcept { return n_; } usize size(u32 v) { assert(v < n_); return static_cast<usize>(-data_[leader(v)]); } inline usize components() const noexcept { return comps_; } std::vector<std::vector<u32>> enumerate() { std::vector<std::vector<u32>> res(n_); for (u32 v{} ; v < n_ ; v++) { res[leader(v)].push_back(v); } res.erase(std::remove_if(res.begin(), res.end(), [](const auto& arr) -> bool { return arr.empty(); }), res.end()); return res; } private: usize n_{}, comps_{}; std::vector<i32> data_; }; } // namespace zawa using namespace zawa; // #include "atcoder/modint" // using mint = atcoder::modint998244353; int N, M; std::tuple<int, int, int> E[200020]; int main() { std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios::sync_with_stdio(false); std::cin >> N >> M; for (int i = 0 ; i < M ; i++) { int u, v, c; std::cin >> u >> v >> c; u--; v--; E[i] = {c, u, v}; } std::sort(E, E + M); std::reverse(E, E + M); DisjointSetUnion dsu(N); long long ans = 0; for (int i = 0 ; i < M ; i++) { auto [c, u, v] = E[i]; if (dsu.same(u, v)) continue; dsu.merge(u, v); ans += c + c; } std::cout << ans << '\n'; }