結果
問題 | No.2202 贅沢てりたまチキン |
ユーザー |
![]() |
提出日時 | 2023-06-11 14:11:27 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 915 ms / 2,000 ms |
コード長 | 1,676 bytes |
コンパイル時間 | 352 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 90,740 KB |
最終ジャッジ日時 | 2025-01-03 03:50:44 |
合計ジャッジ時間 | 7,467 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
# coding: utf-8# Your code here!class UnionFind():# 初期化def __init__(self, n):self.par = [-1] * nself.rank = [0] * nself.siz = [1] * n# 根を求めるdef root(self, x):if self.par[x] == -1: return x # x が根の場合は x を返すelse:self.par[x] = self.root(self.par[x]) # 経路圧縮return self.par[x]# x と y が同じグループに属するか (根が一致するか)def issame(self, x, y):return self.root(x) == self.root(y)# x を含むグループと y を含むグループを併合するdef unite(self, x, y):# x 側と y 側の根を取得するrx = self.root(x)ry = self.root(y)if rx == ry: return False # すでに同じグループのときは何もしない# union by rankif self.rank[rx] < self.rank[ry]: # ry 側の rank が小さくなるようにするrx, ry = ry, rxself.par[ry] = rx # ry を rx の子とするif self.rank[rx] == self.rank[ry]: # rx 側の rank を調整するself.rank[rx] += 1self.siz[rx] += self.siz[ry] # rx 側の siz を調整するreturn True# x を含む根付き木のサイズを求めるdef size(self, x):return self.siz[self.root(x)]N,M=map(int,input().split())uf=UnionFind(2*N)for _ in range(M):A,B=map(int,input().split())A-=1B-=1r_A=2*N-A-1r_B=2*N-B-1uf.unite(A,r_B)uf.unite(B,r_A)for i in range(N):if not uf.issame(i,2*N-i-1):print("No")exit()print("Yes")