結果
問題 | No.2286 Join Hands |
ユーザー | 👑 rin204 |
提出日時 | 2024-04-29 21:45:13 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,993 bytes |
コンパイル時間 | 157 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 92,652 KB |
最終ジャッジ日時 | 2024-04-29 21:45:26 |
合計ジャッジ時間 | 12,561 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 102 ms
79,488 KB |
testcase_01 | AC | 91 ms
75,648 KB |
testcase_02 | AC | 93 ms
75,648 KB |
testcase_03 | AC | 102 ms
79,232 KB |
testcase_04 | AC | 102 ms
79,488 KB |
testcase_05 | AC | 103 ms
79,488 KB |
testcase_06 | AC | 104 ms
79,232 KB |
testcase_07 | AC | 105 ms
79,488 KB |
testcase_08 | AC | 205 ms
85,596 KB |
testcase_09 | AC | 221 ms
86,244 KB |
testcase_10 | AC | 272 ms
87,896 KB |
testcase_11 | AC | 263 ms
88,572 KB |
testcase_12 | AC | 243 ms
87,424 KB |
testcase_13 | AC | 248 ms
86,784 KB |
testcase_14 | AC | 252 ms
87,884 KB |
testcase_15 | AC | 263 ms
87,764 KB |
testcase_16 | AC | 259 ms
87,540 KB |
testcase_17 | AC | 216 ms
86,312 KB |
testcase_18 | AC | 236 ms
87,424 KB |
testcase_19 | AC | 210 ms
86,400 KB |
testcase_20 | AC | 220 ms
86,656 KB |
testcase_21 | AC | 270 ms
87,912 KB |
testcase_22 | AC | 218 ms
86,400 KB |
testcase_23 | AC | 205 ms
86,144 KB |
testcase_24 | AC | 240 ms
87,296 KB |
testcase_25 | AC | 211 ms
85,888 KB |
testcase_26 | AC | 202 ms
85,120 KB |
testcase_27 | AC | 208 ms
86,144 KB |
testcase_28 | AC | 93 ms
75,776 KB |
testcase_29 | AC | 101 ms
79,232 KB |
testcase_30 | AC | 102 ms
79,616 KB |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | AC | 102 ms
79,488 KB |
testcase_34 | AC | 103 ms
79,360 KB |
testcase_35 | WA | - |
testcase_36 | AC | 104 ms
79,616 KB |
testcase_37 | WA | - |
testcase_38 | AC | 103 ms
79,232 KB |
testcase_39 | AC | 102 ms
79,488 KB |
testcase_40 | WA | - |
testcase_41 | AC | 105 ms
79,360 KB |
testcase_42 | AC | 103 ms
79,616 KB |
testcase_43 | WA | - |
testcase_44 | AC | 103 ms
79,488 KB |
testcase_45 | WA | - |
testcase_46 | WA | - |
testcase_47 | AC | 201 ms
87,936 KB |
testcase_48 | RE | - |
testcase_49 | AC | 203 ms
88,064 KB |
testcase_50 | WA | - |
testcase_51 | AC | 129 ms
81,152 KB |
testcase_52 | AC | 184 ms
84,224 KB |
testcase_53 | AC | 218 ms
88,064 KB |
testcase_54 | AC | 224 ms
86,784 KB |
testcase_55 | AC | 220 ms
87,296 KB |
testcase_56 | AC | 203 ms
87,680 KB |
testcase_57 | AC | 203 ms
87,936 KB |
testcase_58 | RE | - |
testcase_59 | AC | 202 ms
87,808 KB |
testcase_60 | AC | 194 ms
88,064 KB |
ソースコード
from collections import deque from dataclasses import dataclass class mf_graph: @dataclass class edge: from_: int to: int cap: int flow: int # def __init__(self, from_, to, cap, flow): # self.from_ = from_ # self.to = to # self.cap = cap # self.flow = flow @dataclass class _edge: to: int rev: int cap: int # def __init__(self, to, rev, cap): # self.to = to # self.rev = rev # self.cap = cap def __init__(self, n): self.n = n self.G = [[] for _ in range(n)] self.pos = [] def add_edge(self, from_, to, cap): m = len(self.pos) self.pos.append((from_, len(self.G[from_]))) from_id = len(self.G[from_]) to_id = len(self.G[to]) if from_ == to: to_id += 1 self.G[from_].append(mf_graph._edge(to, to_id, cap)) self.G[to].append(mf_graph._edge(from_, from_id, 0)) return m def get_edge(self, i): _e = self.G[self.pos[i][0]][self.pos[i][1]] _re = self.G[_e.to][_e.rev] return mf_graph.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap) def edges(self): m = len(self.pos) result = [] for i in range(m): result.append(self.get_edge(i)) return result def change_edge(self, i, new_cap, new_flow): _e = self.G[self.pos[i][0]][self.pos[i][1]] self.G[_e.to][_e.rev].cap = new_flow self.G[self.pos[i][0]][self.pos[i][1]].cap = new_cap - new_flow def flow(self, s, t, flow_limit=1 << 60): level = [] iter = [] que = deque() def bfs(): nonlocal level level = [-1] * self.n level[s] = 0 que.clear() que.append(s) while que: v = que.popleft() for e in self.G[v]: if e.cap == 0 or level[e.to] >= 0: continue level[e.to] = level[v] + 1 if e.to == t: return que.append(e.to) def dfs(v, up): if v == s: return up nonlocal level, iter res = 0 level_v = level[v] while iter[v] < len(self.G[v]): i = iter[v] iter[v] += 1 e = self.G[v][i] if level_v <= level[e.to] or self.G[e.to][e.rev].cap == 0: continue d = dfs(e.to, min(up - res, self.G[e.to][e.rev].cap)) if d <= 0: continue self.G[v][i].cap += d self.G[e.to][e.rev].cap -= d res += d if res == up: return res level[v] = self.n return res flow = 0 while flow < flow_limit: bfs() if level[t] == -1: break iter = [0] * self.n f = dfs(t, flow_limit - flow) if f == 0: break flow += f return flow def min_cut(self, s): visited = [False] * self.n que = deque() que.append(s) while que: p = que.popleft() visited[p] = True for e in self.G[p]: if e.cap and not visited[e.to]: visited[e.to] = True que.append(e.to) return visited n, m = map(int, input().split()) G = mf_graph(2 * n + 2) s = 2 * n t = s + 1 for i in range(n): G.add_edge(s, i, 1) G.add_edge(n + i, t, 1) for i in range(m): u, v = map(int, input().split()) u -= 1 v -= 1 G.add_edge(u, n + v, 1) G.add_edge(v, n + u, 1) res = G.flow(s, t) if res == n - 1: res = n - 2 ans = res - (n - res) print(ans)