結果

問題 No.1805 Approaching Many Typhoon
ユーザー KnotsKnots
提出日時 2022-02-12 22:04:51
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,466 bytes
コンパイル時間 2,175 ms
コンパイル使用メモリ 207,412 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-29 01:14:48
合計ジャッジ時間 3,395 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 1 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 1 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 1 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 1 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 1 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 1 ms
5,376 KB
testcase_26 AC 1 ms
5,376 KB
testcase_27 AC 1 ms
5,376 KB
testcase_28 AC 3 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 3 ms
5,376 KB
testcase_31 AC 2 ms
5,376 KB
testcase_32 AC 1 ms
5,376 KB
testcase_33 AC 1 ms
5,376 KB
testcase_34 AC 2 ms
5,376 KB
testcase_35 AC 2 ms
5,376 KB
testcase_36 AC 2 ms
5,376 KB
testcase_37 AC 2 ms
5,376 KB
testcase_38 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int INF = (1<<30)-1;
const int MOD = 1e9+7;
const ll LINF = (1ll<<62)-1;

#define REP(i,n) for(int i=0;i<(n);++i)
#define COUT(x) cout<<(x)<<"\n"
#define COUT16(x) cout << fixed << setprecision(16) << (x) << "\n";

//Union-Find
/*　
    連結成分に操作する際に利用する可能性が高い
    is_same(x,y):x,yが同じ集合にいるか
    unite(x,y):x,yを同じ集合にする
    treesize(x):xを含む集合の要素数
*/
struct UnionFind{
    vector<int> size,parents;
    UnionFind() {}
    UnionFind(int n){
        size.resize(n,0);
        parents.resize(n,0);
        for(int i=0;i<n;i++){
            makeTree(i);
        }
    }
    void makeTree(int x){
        parents[x] = x; //xの親はx
        size[x] = 1; //初期値の木のサイズは1
    }
    bool is_same(int x,int y){
        if(findroot(x)==findroot(y))return 1;///xとyの親が一緒なら1を返す
        else return 0;
    }
    bool unite(int x,int y){
        x = findroot(x);
        y = findroot(y);
        if(x==y)return 0;//xとyが同じならスルー
        //計算量逓減のために木の高さが低い方を高い方に接続
        if(size[x]>size[y]){
            parents[y] = x;
            size[x] += size[y];
        }
        else{
            parents[x] = y;
            size[y] += size[x];
        }
        return 1;//処理を終えた後,接続したことをreturn1で返す
    }
    int findroot(int x){
        if(x != parents[x]){
            parents[x] = findroot(parents[x]);
        }
        return parents[x];
    }
    int treesize(int x){
        return size[findroot(x)];
    }
};

int main(){
    int n,m,F,T,u,p;cin >> n >> m;
    vector<int> f(m+1),t(m+1),I;
    for(int i=0;i<m+1;i++){
        cin >> F >> T;
        f[i] = F-1;
        t[i] = T-1;
    }
    cin >> u;
    REP(i,u){
        cin >> p;
        I.push_back(p-1);
    }
    UnionFind uf(n);
    for(int i=1;i<m+1;i++){
        bool flag = 1;
        for(int j=0;j<u;j++){
            if(I[j]==t[i] || I[j]==f[i]){
                flag = 0;
            }
        }
        if(flag)uf.unite(f[i],t[i]);
    }
    if(uf.is_same(f[0],t[0])) cout << "Yes" << endl;
    else cout << "No" << endl;
}
0