結果

問題 No.2664 Prime Sum
ユーザー なえしらなえしら
提出日時 2024-07-24 00:19:10
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,193 bytes
コンパイル時間 767 ms
コンパイル使用メモリ 82,464 KB
実行使用メモリ 72,256 KB
最終ジャッジ日時 2024-07-24 00:19:15
合計ジャッジ時間 4,481 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
53,948 KB
testcase_01 WA -
testcase_02 AC 39 ms
53,568 KB
testcase_03 AC 39 ms
53,536 KB
testcase_04 AC 39 ms
53,968 KB
testcase_05 AC 53 ms
62,352 KB
testcase_06 AC 48 ms
56,636 KB
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 AC 45 ms
56,716 KB
testcase_13 AC 53 ms
62,828 KB
testcase_14 AC 70 ms
69,640 KB
testcase_15 AC 69 ms
69,792 KB
testcase_16 AC 68 ms
69,628 KB
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 49 ms
58,020 KB
testcase_23 AC 67 ms
70,472 KB
testcase_24 WA -
testcase_25 WA -
testcase_26 AC 40 ms
54,124 KB
testcase_27 AC 43 ms
54,308 KB
testcase_28 AC 40 ms
53,760 KB
testcase_29 AC 40 ms
54,580 KB
testcase_30 AC 39 ms
55,296 KB
testcase_31 WA -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 AC 38 ms
53,308 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[-1][3]


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)

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