結果
問題 |
No.1639 最小通信路
|
ユーザー |
![]() |
提出日時 | 2023-06-08 22:04:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 11 ms / 2,000 ms |
コード長 | 1,286 bytes |
コンパイル時間 | 955 ms |
コンパイル使用メモリ | 109,628 KB |
最終ジャッジ日時 | 2025-02-13 23:26:42 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 43 |
ソースコード
#include <iostream> #include <vector> #include <cmath> #include <map> #include <set> #include <iomanip> #include <queue> #include <algorithm> #include <numeric> #include <deque> using namespace std; using ll = long long; struct UnionFind { vector<int> par; vector<int> siz; UnionFind(int N) : par(N), siz(N) { for(int i = 0; i < N; i++){ par[i] = i; siz[i] = 1; } } int root(int x) { if (par[x] == x) return x; return par[x] = root(par[x]); } void unite(int x, int y) { int rx = root(x); int ry = root(y); if (rx == ry) return; par[rx] = ry; siz[ry] += siz[rx]; } bool same(int x, int y) { int rx = root(x); int ry = root(y); return rx == ry; } int size(int x){ return siz[root(x)]; } }; template<typename T> using pq = priority_queue<T, vector<T>, greater<T>>; int main(){ ll N, M, R, x, y; string c; cin >> N; pq<tuple<ll, ll, ll>> que; UnionFind tree(N+1); for (int i=0; i<N*(N-1)/2; i++){ cin >> x >> y >> c; tree.unite(x, y); if (tree.size(1) == N){ cout << c << endl; return 0; } } return 0; }