結果

問題 No.654 Air E869120
ユーザー Mao-betaMao-beta
提出日時 2020-09-24 00:26:58
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 963 ms / 2,000 ms
コード長 5,099 bytes
コンパイル時間 103 ms
コンパイル使用メモリ 11,492 KB
実行使用メモリ 182,848 KB
最終ジャッジ日時 2023-09-10 13:14:41
合計ジャッジ時間 9,949 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 21 ms
9,120 KB
testcase_01 AC 22 ms
9,096 KB
testcase_02 AC 21 ms
9,288 KB
testcase_03 AC 22 ms
9,280 KB
testcase_04 AC 22 ms
9,104 KB
testcase_05 AC 22 ms
9,264 KB
testcase_06 AC 21 ms
9,108 KB
testcase_07 AC 21 ms
9,320 KB
testcase_08 AC 21 ms
9,272 KB
testcase_09 AC 21 ms
9,092 KB
testcase_10 AC 246 ms
10,244 KB
testcase_11 AC 163 ms
10,276 KB
testcase_12 AC 178 ms
10,108 KB
testcase_13 AC 224 ms
10,140 KB
testcase_14 AC 171 ms
10,220 KB
testcase_15 AC 167 ms
10,100 KB
testcase_16 AC 222 ms
13,312 KB
testcase_17 AC 250 ms
13,292 KB
testcase_18 AC 223 ms
13,308 KB
testcase_19 AC 236 ms
13,044 KB
testcase_20 AC 116 ms
16,120 KB
testcase_21 AC 138 ms
16,128 KB
testcase_22 AC 59 ms
16,060 KB
testcase_23 AC 82 ms
16,000 KB
testcase_24 AC 136 ms
16,136 KB
testcase_25 AC 56 ms
16,176 KB
testcase_26 AC 73 ms
16,132 KB
testcase_27 AC 60 ms
18,800 KB
testcase_28 AC 97 ms
19,476 KB
testcase_29 AC 62 ms
18,932 KB
testcase_30 AC 963 ms
182,848 KB
testcase_31 AC 947 ms
182,812 KB
testcase_32 AC 933 ms
182,732 KB
testcase_33 AC 930 ms
151,604 KB
testcase_34 AC 946 ms
182,796 KB
testcase_35 AC 20 ms
9,144 KB
testcase_36 AC 22 ms
9,132 KB
testcase_37 AC 21 ms
9,108 KB
testcase_38 AC 21 ms
9,268 KB
testcase_39 AC 22 ms
9,120 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
from collections import defaultdict
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
INF = 10 ** 20
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


class Dinic:
    def __init__(self, n=0):
        self._n = n
        self.g = [[] for _ in range(n)]
        self.pos = []

    def add_edge(self, frm, to, cap):
        m = len(self.pos)
        e1 = Dinic._edge(to, cap)
        e2 = Dinic._edge(frm, 0)
        e1.rev = e2
        e2.rev = e1
        self.pos.append(e1)
        self.g[frm].append(e1)
        self.g[to].append(e2)
        return m

    class edge:
        def __init__(self, frm, to, cap, flow):
            self.frm = frm
            self.to = to
            self.cap = cap
            self.flow = flow

        def __iter__(self):
            yield self.frm
            yield self.to
            yield self.cap
            yield self.flow

    def get_edge(self, i):
        e1 = self.pos[i]
        e2 = e1.rev
        return Dinic.edge(e2.to, e1.to, e1.cap + e2.cap, e2.cap)

    def edges(self):
        return [self.get_edge(i) for i in range(len(self.pos))]

    def change_edge(self, i, new_cap, new_flow):
        e = self.pos[i]
        e.cap = new_cap - new_flow
        e.rev.cap = new_flow

    def flow(self, s, t, flow_limit=0XFFFFFFFFFFFFFFF):
        g = self.g
        flow = 0
        while flow < flow_limit:
            level = [-1] * self._n
            level[s] = 0
            que = [None] * self._n
            ql = 0
            qr = 1
            que[0] = s
            unreached = True
            while unreached and ql < qr:
                v = que[ql]
                ql += 1
                for e in g[v]:
                    to = e.to
                    if e.cap and level[to] < 0:
                        level[to] = level[v] + 1
                        if to == t:
                            unreached = False
                            break
                        que[qr] = to
                        qr += 1
            if unreached:
                return flow
            ptr = [len(es) for es in g]
            stack = []
            v = t
            up = flow_limit - flow
            res = 0
            while True:
                if v == s or not ptr[v]:
                    if v == s:
                        res = up
                    while stack:
                        tmp = res
                        e, up, res = stack.pop()
                        e.cap -= tmp
                        e.rev.cap += tmp
                        res += tmp
                        if res < up:
                            v = e.to
                            break
                    else:
                        flow += res
                        break
                i = ptr[v]
                while i:
                    i -= 1
                    e = g[v][i]
                    if level[e.to] == level[v] - 1 and e.rev.cap:
                        ptr[v] = i
                        stack.append((e.rev, up, res))
                        v = e.to
                        up = min(up, e.rev.cap)
                        res = 0
                        break
                else:
                    ptr[v] = i
        return flow

    def min_cut(self, s):
        visited = [False] * self._n
        que = [None] * self._n
        ql = 0
        qr = 1
        que[0] = s
        visited[s] = True
        while ql < qr:
            p = que[ql]
            ql += 1
            for e in self.g[p]:
                if e.cap and not visited[e.to]:
                    visited[e.to] = True
                    que[qr] = e.to
                    qr += 1
        return visited

    class _edge:
        def __init__(self, to, cap):
            self.to = to
            self.cap = cap


def compress(S):
    """ 座標圧縮 """

    zipped, unzipped = {}, {}
    for i, a in enumerate(sorted(S)):
        zipped[a] = i
        unzipped[i] = a
    return zipped, unzipped


def main():
    N, M, d = NMI()
    time_set = set()
    edges = []
    for i in range(M):
        u, v, p, q, w = NMI()
        u, v = u-1, v-1
        q = q + d
        time_set.add(p)
        time_set.add(q)
        edges.append([u, v, p, q, w])
    time_zip, time_unzip = compress(time_set)
    T = len(time_zip)
    din = Dinic(N*T)
    flight_times = [[] for _ in range(N)]
    for u, v, p, q, w in edges:
        p = time_zip[p]
        q = time_zip[q]
        din.add_edge(u*T+p, v*T+q, w)
        flight_times[u].append(p)
        flight_times[v].append(q)
    for n in range(N):
        flight_times[n].sort()
        f_len = len(flight_times[n])
        for f in range(f_len-1):
            p, q = flight_times[n][f], flight_times[n][f+1]
            din.add_edge(n*T+p, n*T+q, INF)

    if not flight_times[0] or not flight_times[-1]:
        print(0)
        exit()

    print(din.flow(0*T+flight_times[0][0], (N-1)*T+flight_times[N-1][-1]))


if __name__ == "__main__":
    main()
0