結果

問題 No.2202 贅沢てりたまチキン
ユーザー zezerozezero
提出日時 2023-02-03 21:53:43
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,454 bytes
コンパイル時間 924 ms
コンパイル使用メモリ 95,736 KB
実行使用メモリ 8,064 KB
最終ジャッジ日時 2024-07-02 19:46:04
合計ジャッジ時間 3,288 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 WA -
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 6 ms
7,936 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 113 ms
8,064 KB
testcase_15 AC 115 ms
7,936 KB
testcase_16 AC 89 ms
8,064 KB
testcase_17 AC 92 ms
7,936 KB
testcase_18 AC 45 ms
5,760 KB
testcase_19 AC 60 ms
8,064 KB
testcase_20 WA -
testcase_21 AC 116 ms
7,936 KB
testcase_22 AC 76 ms
5,376 KB
testcase_23 AC 91 ms
5,376 KB
testcase_24 AC 84 ms
5,376 KB
testcase_25 AC 127 ms
7,936 KB
testcase_26 WA -
testcase_27 AC 112 ms
8,064 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i=0;i < (int)(n);i++)

class union_find {
public:
vector<int> par,rank,lsize;
union_find(int n): par(n),rank(n),lsize(n){
   for (int i=0;i < n;i++){
      par[i]=i;
      rank[i]=0;
      lsize[i]=1;
   }
}

int find(int x){
   if (par[x]==x){
      return x;
   }
   else{
      return par[x] = find(par[x]); 
   }
}

void unite(int x ,int y){
   x=find(x);
   y=find(y);
   if (x==y) return;
   if (rank[x] < rank[y]){
      lsize[y] += lsize[x];
      lsize[x] = -1;
      par[x] = y;
   }else{
      lsize[x] += lsize[y];
      lsize[y] = -1;
      par[y]=x;
      if (rank[x]==rank[y]) rank[x]++;
   }   
}

bool same(int x, int y){
   return find(x) == find(y);
}

int size(int x){
   if (lsize[x] == -1){
      x=find(x);
   }
   return lsize[x];
}

int groups(){
   int res = 0;
   for (int i = 0;i < par.size();i++){
      if (i == par[i]) res++;
   }
   return res;
}

};

void solve(){
  int n,m;
  cin >> n >> m;
  union_find d(2*n);
  for (int i = 0; i < m;i++){
    int a,b;
    cin >> a >> b;
    a--;b--;
    d.unite(a,b+n);
    d.unite(a+n,b);
  }
  if (d.groups() == 1){
    cout << "Yes\n";
  }
  else cout << "No\n";

  return;
}

  

int main(){
  int tt = 1;
  //cin >> tt;
  while(tt--){
	  solve();
  }
  return 0;
}
0