結果
問題 |
No.1805 Approaching Many Typhoon
|
ユーザー |
![]() |
提出日時 | 2024-05-26 12:10:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,766 bytes |
コンパイル時間 | 1,786 ms |
コンパイル使用メモリ | 171,228 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-12-20 20:15:11 |
合計ジャッジ時間 | 3,413 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 2 |
other | AC * 25 WA * 6 RE * 4 |
ソースコード
#include<bits/stdc++.h> using namespace std; struct UnionFind { vector<int> par, rank, siz; UnionFind(int n) : par(n,-1), rank(n,0), siz(n,1) { } int root(int x) { if (par[x]==-1) return x; // x が根の場合は x を返す else return par[x] = root(par[x]); // 経路圧縮 } bool issame(int x, int y) { return root(x)==root(y); } bool unite(int x, int y) { int rx = root(x), ry = root(y); // x 側と y 側の根を取得する if (rx==ry) return false; // すでに同じグループのときは何もしない // union by rank if (rank[rx]<rank[ry]) swap(rx, ry); // ry 側の rank が小さくなるようにする par[ry] = rx; // ry を rx の子とする if (rank[rx]==rank[ry]) rank[rx]++; // rx 側の rank を調整する siz[rx] += siz[ry]; // rx 側の siz を調整する return true; } int size(int x) { return siz[root(x)]; } }; int main(){ int N,M,S,G,f,t; cin >> N >> M >> S >> G; vector<int> edge_f(M),edge_t(M); for(int i=0;i<M;i++){ cin >> f >> t; edge_f[i] = f-1; edge_t[i] = t-1; } int U,iii; cin >> U; vector<int> I(U); for(int i=0;i<U;i++){ cin >> iii; I[i] = iii-1; } UnionFind u(N); int flg = 0; for(int i=0;i<M;i++){ for(int j=0;j<U;j++){ if(edge_f[i] == I[j]){ flg = 1; } if(edge_t[i] == I[j]){ flg = 1; } } if(flg == 0){ u.unite(edge_f[i],edge_t[i]); } flg = 0; } if(u.issame(S,G)){ cout << "Yes" << endl; } else { cout << "No" << endl; } }