結果
問題 |
No.1639 最小通信路
|
ユーザー |
![]() |
提出日時 | 2021-08-18 00:18:26 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 16 ms / 2,000 ms |
コード長 | 876 bytes |
コンパイル時間 | 4,192 ms |
コンパイル使用メモリ | 234,200 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-11 01:02:56 |
合計ジャッジ時間 | 5,777 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 43 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll=long long; using Graph=vector<vector<int>>; #define MAX 2000000 #define MOD 1000000007 #define INF 1000000000000000000 vector<int> parent; vector<int> cnt; int find(int x){ int y=parent[x]; if(y!=parent[y]){ y=find(y); } return parent[x]=y; } void unite(int a,int b){ int x=find(a); int y=find(b); if(x!=y){ parent[y]=x; cnt[x]+=cnt[y]; } } int main(){ int N; cin>>N; vector<int> a(N*(N-1)/2),b(N*(N-1)/2); vector<string> C(N*(N-1)/2); for(int i=0;i<N*(N-1)/2;i++){ cin>>a[i]>>b[i]>>C[i]; a[i]--; b[i]--; } parent.resize(N); iota(parent.begin(),parent.end(),0); cnt.resize(N,1); for(int i=0;i<N*(N-1)/2;i++){ unite(a[i],b[i]); if(cnt[find(a[i])]==N){ cout<<C[i]<<'\n'; return 0; } } }