結果

問題 No.3087 University Coloring
ユーザー zawakasu
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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';
}
0