結果
問題 |
No.3087 University Coloring
|
ユーザー |
![]() |
提出日時 | 2025-04-04 21:50:51 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 257 ms / 2,000 ms |
コード長 | 1,772 bytes |
コンパイル時間 | 4,645 ms |
コンパイル使用メモリ | 289,216 KB |
実行使用メモリ | 7,936 KB |
最終ジャッジ日時 | 2025-04-04 21:51:22 |
合計ジャッジ時間 | 12,052 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <bits/stdc++.h> #define ALL(x) (x).begin(), (x).end() #define LB(v, x) (int)(lower_bound(ALL(v), x) - (v).begin()) #define UQ(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end()) #define IO ios::sync_with_stdio(false), cin.tie(nullptr); #define chmax(a, b) (a) = (a) < (b) ? (b) : (a) #define chmin(a, b) (a) = (a) < (b) ? (a) : (b) using namespace std; using ll = long long; const int INF = 1e9 + 10; const ll INFL = 4e18; struct DSU { DSU() = default; DSU(int n) { par.resize(n); iota(par.begin(), par.end(), 0); sz.assign(n, 1); forest_count = n; } int find(int x) { if (par[x] == x) return x; return par[x] = find(par[x]); } bool merge(int x, int y) { x = find(x), y = find(y); if (x == y) return false; if (sz[x] < sz[y]) swap(x, y); par[y] = x; sz[x] += sz[y]; forest_count--; return true; } int size(int x) { return sz[find(x)]; } bool same(int x, int y) { return find(x) == find(y); } int count() { return forest_count; } vector<vector<int>> groups() { int n = par.size(); vector<vector<int>> ret(n); for (int i = 0; i < n; i++) ret[find(i)].push_back(i); ret.erase(remove_if(ret.begin(), ret.end(), [&](const vector<int>& v) { return v.empty(); }), ret.end()); return ret; } private: vector<int> par, sz; int forest_count; }; int main() { int N, M; cin >> N >> M; vector<tuple<ll, int, int>> E(M); for (auto& [w, u, v] : E) cin >> u >> v >> w, u--, v--; sort(ALL(E)); reverse(ALL(E)); ll ans = 0; DSU dsu(N); for (auto [w, u, v] : E) { if (dsu.merge(u, v)) ans += w; } cout << ans * 2 << endl; }