結果
問題 | No.654 Air E869120 |
ユーザー | maspy |
提出日時 | 2020-03-31 12:52:51 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
AC
|
実行時間 | 166 ms / 2,000 ms |
コード長 | 3,039 bytes |
コンパイル時間 | 95 ms |
コンパイル使用メモリ | 11,244 KB |
実行使用メモリ | 10,228 KB |
最終ジャッジ日時 | 2023-09-06 14:30:01 |
合計ジャッジ時間 | 3,726 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 20 ms
8,764 KB |
testcase_01 | AC | 20 ms
8,808 KB |
testcase_02 | AC | 18 ms
8,820 KB |
testcase_03 | AC | 19 ms
8,804 KB |
testcase_04 | AC | 19 ms
8,788 KB |
testcase_05 | AC | 19 ms
8,804 KB |
testcase_06 | AC | 19 ms
8,864 KB |
testcase_07 | AC | 19 ms
8,744 KB |
testcase_08 | AC | 19 ms
8,792 KB |
testcase_09 | AC | 19 ms
8,768 KB |
testcase_10 | AC | 95 ms
9,312 KB |
testcase_11 | AC | 82 ms
9,348 KB |
testcase_12 | AC | 76 ms
9,444 KB |
testcase_13 | AC | 85 ms
9,488 KB |
testcase_14 | AC | 81 ms
9,284 KB |
testcase_15 | AC | 80 ms
9,528 KB |
testcase_16 | AC | 137 ms
10,116 KB |
testcase_17 | AC | 166 ms
10,124 KB |
testcase_18 | AC | 152 ms
10,192 KB |
testcase_19 | AC | 155 ms
10,176 KB |
testcase_20 | AC | 54 ms
10,216 KB |
testcase_21 | AC | 59 ms
10,100 KB |
testcase_22 | AC | 30 ms
10,128 KB |
testcase_23 | AC | 40 ms
10,228 KB |
testcase_24 | AC | 55 ms
10,096 KB |
testcase_25 | AC | 29 ms
9,936 KB |
testcase_26 | AC | 35 ms
10,092 KB |
testcase_27 | AC | 27 ms
10,116 KB |
testcase_28 | AC | 31 ms
9,992 KB |
testcase_29 | AC | 27 ms
9,904 KB |
testcase_30 | AC | 25 ms
9,984 KB |
testcase_31 | AC | 25 ms
10,028 KB |
testcase_32 | AC | 26 ms
9,936 KB |
testcase_33 | AC | 25 ms
9,812 KB |
testcase_34 | AC | 26 ms
10,016 KB |
testcase_35 | AC | 19 ms
8,844 KB |
testcase_36 | AC | 18 ms
8,740 KB |
testcase_37 | AC | 18 ms
8,760 KB |
testcase_38 | AC | 18 ms
8,844 KB |
testcase_39 | AC | 19 ms
8,820 KB |
ソースコード
#!/usr/bin/ python3.8 import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines from collections import deque class Dinic: def __init__(self, N, source, sink): self.N = N self.G = [[] for _ in range(N)] self.source = source self.sink = sink def add_edge(self, fr, to, cap): n1 = len(self.G[fr]) n2 = len(self.G[to]) self.G[fr].append([to, cap, n2]) self.G[to].append([fr, 0, n1]) # 逆辺を cap 0 で追加 def add_edge_undirected(self, fr, to, cap): n1 = len(self.G[fr]) n2 = len(self.G[to]) self.G[fr].append([to, cap, n2]) self.G[to].append([fr, cap, n1]) def bfs(self): level = [0] * self.N G = self.G; source = self.source; sink = self.sink q = deque([source]) level[source] = 1 pop = q.popleft; append = q.append while q: v = pop() lv = level[v] + 1 for to, cap, rev in G[v]: if not cap: continue if level[to]: continue level[to] = lv if to == sink: self.level = level return append(to) self.level = level def dfs(self, v, f): if v == self.sink: return f G = self.G prog = self.progress level = self.level lv = level[v] E = G[v] for i in range(prog[v], len(E)): to, cap, rev = E[i] prog[v] = i if not cap: continue if level[to] <= lv: continue x = f if f < cap else cap ff = self.dfs(to, x) if ff: E[i][1] -= ff G[to][rev][1] += ff return ff return 0 def max_flow(self): INF = 10**18 flow = 0 while True: self.bfs() if not self.level[self.sink]: return flow self.progress = [0] * self.N while True: f = self.dfs(self.source, INF) if not f: break flow += f return flow N, M, D = map(int, readline().split()) m = map(int, read().split()) U, V, P, Q, W = zip(*zip(m, m, m, m, m)) X = [(u << 32) + p for u, p in zip(U, P)] Y = [(v << 32) + q + D for v, q in zip(V, Q)] nodes = sorted(set(X + Y)) ind = {x: i for i, x in enumerate(nodes)} L = len(nodes) source = L sink = L + 1 dinic = Dinic(len(nodes) + 2, source, sink) INF = 10 ** 18 add = dinic.add_edge u, t = divmod(nodes[0], 1 << 32) if u == 1: add(source, 0, INF) u, t = divmod(nodes[-1], 1 << 32) if u == N: add(L - 1, sink, INF) for i, (x, y) in enumerate(zip(nodes, nodes[1:])): if x >> 32 == y >> 32: add(i, i + 1, INF) for x, y, w in zip(X, Y, W): add(ind[x], ind[y], w) f = dinic.max_flow() print(f)