結果

問題 No.2664 Prime Sum
ユーザー なえしらなえしら
提出日時 2024-07-24 00:32:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 82 ms / 2,000 ms
コード長 3,203 bytes
コンパイル時間 674 ms
コンパイル使用メモリ 82,396 KB
実行使用メモリ 73,552 KB
最終ジャッジ日時 2024-07-24 00:32:32
合計ジャッジ時間 3,947 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
53,516 KB
testcase_01 AC 38 ms
53,636 KB
testcase_02 AC 39 ms
54,592 KB
testcase_03 AC 41 ms
54,300 KB
testcase_04 AC 39 ms
54,868 KB
testcase_05 AC 57 ms
65,180 KB
testcase_06 AC 54 ms
64,324 KB
testcase_07 AC 45 ms
55,272 KB
testcase_08 AC 54 ms
64,404 KB
testcase_09 AC 82 ms
64,784 KB
testcase_10 AC 53 ms
64,328 KB
testcase_11 AC 40 ms
55,216 KB
testcase_12 AC 47 ms
56,324 KB
testcase_13 AC 57 ms
65,720 KB
testcase_14 AC 69 ms
71,948 KB
testcase_15 AC 71 ms
73,180 KB
testcase_16 AC 68 ms
71,956 KB
testcase_17 AC 45 ms
56,292 KB
testcase_18 AC 60 ms
66,832 KB
testcase_19 AC 61 ms
68,304 KB
testcase_20 AC 71 ms
72,860 KB
testcase_21 AC 70 ms
71,500 KB
testcase_22 AC 57 ms
65,344 KB
testcase_23 AC 71 ms
73,552 KB
testcase_24 AC 70 ms
73,044 KB
testcase_25 AC 72 ms
70,924 KB
testcase_26 AC 41 ms
55,004 KB
testcase_27 AC 43 ms
56,076 KB
testcase_28 AC 41 ms
54,788 KB
testcase_29 AC 41 ms
53,668 KB
testcase_30 AC 40 ms
54,488 KB
testcase_31 AC 40 ms
54,728 KB
testcase_32 AC 42 ms
56,036 KB
testcase_33 AC 44 ms
55,164 KB
testcase_34 AC 43 ms
54,648 KB
testcase_35 AC 44 ms
56,028 KB
testcase_36 AC 39 ms
53,620 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class DirectedGraph:
  def __init__(self, order):
    self._order = order
    self._size = 0
    self._vertex = [[[], []] for _ in range(order)]
    self._edge = []
  def order(self): return self._order
  def size(self): return self._size
  def __get__(self, key):
    if key == 0: return self._vertex
    elif key == 1: return self._edge
  def add_vertex(self, *args):
    self._order += 1
    self._vertex.append([[], [], *args])
  def add_arc(self, v1, v2, *args):
    e = self._size
    self._size += 1
    self._vertex[v1][0].append(e)
    self._vertex[v2][1].append(e)
    self._edge.append([v1, v2, *args])
  def endpoint(self, e, v=None):
    v1, v2 = self._edge[e][:2]
    if v is None: return v1, v2
    return v ^ v1 ^ v2
  def indegree(self, v):
    return len(self._vertex[v][0])
  def outdegree(self, v):
    return len(self._vertex[v][1])

class UndirectedGraph(DirectedGraph):
  def add_edge(self, v1, v2, *args):
    e = self._size
    self._size += 1
    self._vertex[v1][0].append(e)
    self._vertex[v2][0].append(e)
    self._edge.append([v1, v2, *args])
  def degree(self, v):
    return len(self._vertex[v][0])

class ConnectedComponents(UndirectedGraph):
  def __init__(self, order):
    super().__init__(order)
    self._components = []
    self._component = []
  def build(self):
    for i in range(self._order):
      self._vertex[i][1] = [-1]*2
    self._components.clear()
    self._component.clear()
    for i in range(self._order):
      if self._vertex[i][1][0] != -1: continue
      comp_idx = len(self._components)
      self._vertex[i][1] = [comp_idx, 0]
      que, flg = [i], True
      for v in que:
        v_clr = self._vertex[v][1][1]
        for e in self._vertex[v][0]:
          v2 = self.endpoint(e, v)
          if self._vertex[v2][1][0] == -1:
            self._vertex[v2][1][0] = comp_idx
            if flg: self._vertex[v2][1][1] = v_clr ^ 1
            que.append(v2)
          elif flg and self._vertex[v2][1][1] == v_clr:
            flg = False
      self._components.append([[], [], []])
      self._component.append([len(que), 0])
      for v in que:
        if not flg: self._vertex[v][1][1] = -1
        v_clr = self._vertex[v][1][1]
        self._components[comp_idx][v_clr].append(v)
        self._component[comp_idx][1] += self.degree(v)
      self._component[comp_idx][1] //= 2
  def __call__(self, k=None):
    if k is None: return self._components
    return sum(self._components[k], [])
  def __len__(self):
    return len(self._components)
  def order(self, k=None):
    if k is None: return self._order
    return self._component[k][0]
  def size(self, k=None):
    if k is None: return self._size
    return self._component[k][1]
  def __get__(self, key):
    if key == 2: return self._component
    return super().__get__(key)
  def is_connected(self):
    return len(self._components) <= 1
  def is_bipartite(self, k=None):
    if k is None:
      return all(not comp[-1] for comp in self._components)
    return not self._components[k][-1]


n, m = map(int, input().split())
X = ConnectedComponents(n)

for _ in range(m):
  a, b = map(int, input().split())
  X.add_edge(a-1, b-1)

X.build()
print("Yes" if X.is_bipartite() else "No")
0