結果
問題 | No.654 Air E869120 |
ユーザー | zkou |
提出日時 | 2021-03-13 11:04:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 231 ms / 2,000 ms |
コード長 | 7,479 bytes |
コンパイル時間 | 206 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 78,904 KB |
最終ジャッジ日時 | 2024-10-15 04:10:56 |
合計ジャッジ時間 | 5,492 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 41 ms
53,248 KB |
testcase_01 | AC | 40 ms
53,376 KB |
testcase_02 | AC | 39 ms
53,120 KB |
testcase_03 | AC | 40 ms
53,760 KB |
testcase_04 | AC | 41 ms
53,632 KB |
testcase_05 | AC | 42 ms
53,376 KB |
testcase_06 | AC | 39 ms
53,760 KB |
testcase_07 | AC | 41 ms
53,632 KB |
testcase_08 | AC | 41 ms
53,760 KB |
testcase_09 | AC | 42 ms
53,504 KB |
testcase_10 | AC | 225 ms
78,720 KB |
testcase_11 | AC | 205 ms
78,848 KB |
testcase_12 | AC | 222 ms
77,952 KB |
testcase_13 | AC | 231 ms
78,592 KB |
testcase_14 | AC | 209 ms
78,464 KB |
testcase_15 | AC | 198 ms
78,652 KB |
testcase_16 | AC | 145 ms
78,592 KB |
testcase_17 | AC | 141 ms
77,952 KB |
testcase_18 | AC | 143 ms
77,952 KB |
testcase_19 | AC | 152 ms
77,952 KB |
testcase_20 | AC | 116 ms
78,208 KB |
testcase_21 | AC | 123 ms
78,904 KB |
testcase_22 | AC | 89 ms
77,312 KB |
testcase_23 | AC | 99 ms
77,312 KB |
testcase_24 | AC | 123 ms
78,464 KB |
testcase_25 | AC | 90 ms
77,584 KB |
testcase_26 | AC | 99 ms
77,308 KB |
testcase_27 | AC | 83 ms
76,800 KB |
testcase_28 | AC | 95 ms
77,824 KB |
testcase_29 | AC | 85 ms
77,444 KB |
testcase_30 | AC | 73 ms
73,984 KB |
testcase_31 | AC | 73 ms
73,344 KB |
testcase_32 | AC | 71 ms
72,960 KB |
testcase_33 | AC | 75 ms
74,368 KB |
testcase_34 | AC | 75 ms
73,600 KB |
testcase_35 | AC | 40 ms
53,120 KB |
testcase_36 | AC | 39 ms
52,864 KB |
testcase_37 | AC | 40 ms
53,632 KB |
testcase_38 | AC | 39 ms
53,120 KB |
testcase_39 | AC | 39 ms
53,760 KB |
ソースコード
class mf_graph: """It solves maximum flow problem. """ def __init__(self, n): """It creates a graph of n vertices and 0 edges. Constraints ----------- > 0 <= n <= 10 ** 8 Complexity ---------- > O(n) """ self.n = n self.g = [[] for _ in range(self.n)] self.pos = [] def add_edge(self, from_, to, cap): """It adds an edge oriented from the vertex `from_` to the vertex `to` with the capacity `cap` and the flow amount 0. It returns an integer k such that this is the k-th edge that is added. Constraints ----------- > 0 <= from_, to < n > 0 <= cap Complexity ---------- > O(1) amortized """ # assert 0 <= from_ < self.n # assert 0 <= to < self.n # assert 0 <= 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(self.__class__._edge(to, to_id, cap)) self.g[to].append(self.__class__._edge(from_, from_id, 0)) return m class edge: def __init__(self, from_, to, cap, flow): self.from_ = from_ self.to = to self.cap = cap self.flow = flow def get_edge(self, i): """It returns the current internal state of the edges. The edges are ordered in the same order as added by `add_edge`. Constraints ----------- > 0 <= i < m Complexity ---------- > O(1) """ # assert 0 <= i < len(self.pos) _e = self.g[self.pos[i][0]][self.pos[i][1]] _re = self.g[_e.to][_e.rev] return self.__class__.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap) def edges(self): """It returns the current internal state of the edges. The edges are ordered in the same order as added by `add_edge`. Complexity ---------- > O(m), where m is the number of added edges. """ result = [] for i in range(len(self.pos)): _e = self.g[self.pos[i][0]][self.pos[i][1]] _re = self.g[_e.to][_e.rev] result.append(self.__class__.edge( self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap)) return result def change_edge(self, i, new_cap, new_flow): """It changes the capacity and the flow amount of the i-th edge to `new_cap` and `new_flow`, respectively. It doesn't change the capacity or the flow amount of other edges. See Appendix in the document of AC Library for further details. Constraints ----------- > 0 <= new_flow <= new_cap Complexity ---------- > O(1) """ # assert 0 <= i < len(self.pos) # assert 0 <= new_flow <= new_cap _e = self.g[self.pos[i][0]][self.pos[i][1]] _re = self.g[_e.to][_e.rev] _e.cap = new_cap - new_flow _re.cap = new_flow def _bfs(self, s, t): self.level = [-1] * self.n self.level[s] = 0 q = [s] while q: nq = [] for v in q: for e in self.g[v]: if e.cap and self.level[e.to] == -1: self.level[e.to] = self.level[v] + 1 if e.to == t: return True nq.append(e.to) q = nq return False def _dfs(self, s, t, up): st = [t] while st: v = st[-1] if v == s: st.pop() flow = up for w in st: e = self.g[w][self.it[w]] flow = min(flow, self.g[e.to][e.rev].cap) for w in st: e = self.g[w][self.it[w]] e.cap += flow self.g[e.to][e.rev].cap -= flow return flow while self.it[v] < len(self.g[v]): e = self.g[v][self.it[v]] w = e.to cap = self.g[e.to][e.rev].cap if cap and self.level[v] > self.level[w]: st.append(w) break self.it[v] += 1 else: st.pop() self.level[v] = self.n return 0 def flow(self, s, t, flow_limit=float('inf')): """It augments the flow from s to t as much as possible. It returns the amount of the flow augmented. You may call it multiple times. See Appendix in the document of AC Library for further details. Constraints ----------- > s != t Complexity ---------- > O(min(n^(2/3)m, m^(3/2))) (if all the capacities are 1) or > O(n^2 m) (general), where m is the number of added edges. """ # assert 0 <= s < self.n # assert 0 <= t < self.n # assert s != t flow = 0 while flow < flow_limit and self._bfs(s, t): self.it = [0] * self.n while flow < flow_limit: f = self._dfs(s, t, flow_limit - flow) if not f: break flow += f return flow def min_cut(self, s): """It returns a list of length n, such that the i-th element is `True` if and only if there is a directed path from s to i in the residual network. The returned list corresponds to a s−t minimum cut after calling flow(s, t) exactly once without flow_limit. See Appendix in the document of AC Library for further details. Complexity ---------- > O(n + m), where m is the number of added edges. """ visited = [False] * self.n q = [s] while q: nq = [] for p in q: visited[p] = True for e in self.g[p]: if e.cap and not visited[e.to]: nq.append(e.to) q = nq return visited class _edge: def __init__(self, to, rev, cap): self.to = to self.rev = rev self.cap = cap def main(): import sys import bisect input = sys.stdin.buffer.readline N, M, d = map(int, input().split()) uvpqws = [tuple(map(int, input().split())) for _ in range(M)] ts = [[] for _ in range(N)] ts[0].append(0) ts[N - 1].append(10 ** 9 + d) for u, v, p, q, w in uvpqws: u -= 1; v -= 1 ts[u].append(p) ts[v].append(q + d) ts_list = [] start = [0] for t in ts: ts_list.extend(sorted(t)) start.append(start[-1] + len(t)) g = mf_graph(len(ts_list)) for i in range(N): for j in range(start[i], start[i + 1] - 1): g.add_edge(j, j + 1, float('inf')) for u, v, p, q, w in uvpqws: u -= 1; v -= 1 i = bisect.bisect_left(ts_list, p, start[u], start[u + 1]) j = bisect.bisect_left(ts_list, q + d, start[v], start[v + 1]) assert ts_list[i] == p assert ts_list[j] == q + d g.add_edge(i, j, w) print(g.flow(0, len(ts_list) - 1)) main()