結果
問題 | No.1639 最小通信路 |
ユーザー |
|
提出日時 | 2021-08-06 22:29:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 2,000 ms |
コード長 | 1,183 bytes |
コンパイル時間 | 2,397 ms |
コンパイル使用メモリ | 215,616 KB |
最終ジャッジ日時 | 2025-01-23 15:51:22 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 43 |
ソースコード
#pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef unsigned long long ull; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll myRand(ll B) { return (ull)rng() % B; } struct UnionFind{ vector<int> par,num; UnionFind(int n):par(n),num(n,1){ iota(par.begin(),par.end(),0); //include<numeric> } int find(int v){ return (par[v]==v)?v:(par[v]=find(par[v])); } void unite(int u,int v){ u=find(u),v=find(v); if(u==v)return; if(num[u]<num[v])swap(u,v); num[u]+=num[v]; par[v]=u; } bool same(int u,int v){ return find(u) == find(v); } int size(int v){ return num[find(v)]; } }; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; UnionFind uf(n); int cnt=0; for(int i=0;i<n*(n-1)/2;i++){ int x,y; cin >> x >> y; x--; y--; if(!uf.same(x,y)){ uf.unite(x,y); cnt++; } string s; cin >> s; if(cnt==n-1){ cout << s << endl; cnt=n; } } }