Submission #00011
ソースコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | #include<bits/stdc++.h> using namespace std; struct UnionFind { vector< int > par; vector< int > size; UnionFind( int n) { par.resize(n + 1, -1); //親保存配列 size.resize(n + 1, 1); //木のサイズ } int root( int x) { //親調べ while (1) { if (par[x] == -1) { return (x); } x = par[x]; } } void unite( int u, int v) { //木の接続 int RootU = root(u), RootV = root(v); if (RootU == RootV) { return ; } if (size[RootU] < size[RootV]) { par[RootU] = RootV; size[RootV] += size[RootU]; } else { par[RootV] = RootU; size[RootU] += size[RootV]; } return ; } }; main(){ int n;cin>>n; vector<pair< int ,pair< int , int >>>v; for ( int i=1;i<n;i++){ for ( int j=i+1;j<=n;j++){ int c;cin>>c; v.push_back({c,{i,j}}); } } sort(v.begin(),v.end()); UnionFind g(n+1); int ans=0; for ( int i=0;i<v.size();i++){ if (g.root(v[i].second.first) != g.root(v[i].second.second)){ g.unite(v[i].second.first,v[i].second.second); ans+=v[i].first; } } cout<<ans<< "\n" ; } |
ステータス
項目 | データ |
---|---|
問題 | 0006 - Connect Stations |
ユーザー名 | ei2326 |
投稿日時 | 2024-08-09 10:19:23 |
言語 | C++17 |
状態 | Wrong Answer |
得点 | 0 |
ソースコード長 | 1338 Byte |
最大実行時間 | 204 ms |
最大メモリ使用量 | 14220 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 0 / 10 | * |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
in1.txt | AC | 17 ms | 604 KB |
1
|
in2.txt | AC | 24 ms | 576 KB |
1
|
in3.txt | AC | 18 ms | 412 KB |
1
|
in4.txt | AC | 19 ms | 508 KB |
1
|
in5.txt | AC | 25 ms | 604 KB |
1
|
in6.txt | AC | 19 ms | 680 KB |
1
|
in7.txt | AC | 155 ms | 8024 KB |
1
|
in8.txt | AC | 170 ms | 14220 KB |
1
|
in9.txt | WA | 204 ms | 14024 KB |
1
|