結果

問題 No.1805 Approaching Many Typhoon
ユーザー KnotsKnots
提出日時 2022-02-12 22:00:13
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 2,465 bytes
コンパイル時間 2,201 ms
コンパイル使用メモリ 205,380 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-11 10:26:51
合計ジャッジ時間 5,801 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 RE -
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 RE -
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 2 ms
4,380 KB
testcase_15 AC 1 ms
4,376 KB
testcase_16 AC 1 ms
4,376 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 2 ms
4,376 KB
testcase_20 AC 1 ms
4,376 KB
testcase_21 RE -
testcase_22 RE -
testcase_23 AC 2 ms
4,380 KB
testcase_24 AC 1 ms
4,380 KB
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 AC 2 ms
4,376 KB
testcase_29 AC 3 ms
4,376 KB
testcase_30 AC 2 ms
4,376 KB
testcase_31 AC 3 ms
4,376 KB
testcase_32 AC 2 ms
4,380 KB
testcase_33 AC 2 ms
4,376 KB
testcase_34 AC 2 ms
4,380 KB
testcase_35 AC 2 ms
4,376 KB
testcase_36 AC 2 ms
4,380 KB
testcase_37 AC 2 ms
4,376 KB
testcase_38 AC 2 ms
4,384 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;
        t[i] = T;
    }
    cin >> u;
    REP(i,u){
        cin >> p;
        I.push_back(p);
    }
    
    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