結果
問題 | No.654 Air E869120 |
ユーザー | りん |
提出日時 | 2023-07-09 17:00:07 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 3,585 bytes |
コンパイル時間 | 551 ms |
コンパイル使用メモリ | 86,864 KB |
実行使用メモリ | 186,644 KB |
最終ジャッジ日時 | 2023-09-30 20:25:13 |
合計ジャッジ時間 | 8,474 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 94 ms
71,300 KB |
testcase_01 | AC | 97 ms
71,632 KB |
testcase_02 | AC | 94 ms
71,500 KB |
testcase_03 | AC | 92 ms
71,432 KB |
testcase_04 | AC | 92 ms
71,324 KB |
testcase_05 | AC | 92 ms
71,328 KB |
testcase_06 | AC | 104 ms
76,580 KB |
testcase_07 | AC | 92 ms
71,648 KB |
testcase_08 | AC | 93 ms
71,396 KB |
testcase_09 | AC | 93 ms
71,452 KB |
testcase_10 | AC | 220 ms
78,844 KB |
testcase_11 | AC | 207 ms
79,372 KB |
testcase_12 | AC | 211 ms
79,248 KB |
testcase_13 | AC | 222 ms
79,476 KB |
testcase_14 | AC | 198 ms
79,052 KB |
testcase_15 | AC | 191 ms
78,664 KB |
testcase_16 | AC | 230 ms
113,312 KB |
testcase_17 | AC | 238 ms
113,156 KB |
testcase_18 | AC | 235 ms
114,196 KB |
testcase_19 | AC | 232 ms
113,572 KB |
testcase_20 | AC | 186 ms
110,488 KB |
testcase_21 | AC | 196 ms
119,576 KB |
testcase_22 | AC | 154 ms
90,716 KB |
testcase_23 | AC | 166 ms
93,652 KB |
testcase_24 | AC | 198 ms
116,484 KB |
testcase_25 | AC | 146 ms
86,804 KB |
testcase_26 | AC | 158 ms
91,552 KB |
testcase_27 | AC | 137 ms
83,696 KB |
testcase_28 | AC | 165 ms
100,980 KB |
testcase_29 | AC | 137 ms
83,676 KB |
testcase_30 | AC | 235 ms
186,400 KB |
testcase_31 | AC | 235 ms
186,644 KB |
testcase_32 | AC | 232 ms
186,576 KB |
testcase_33 | RE | - |
testcase_34 | AC | 233 ms
186,580 KB |
testcase_35 | AC | 90 ms
71,176 KB |
testcase_36 | AC | 91 ms
71,444 KB |
testcase_37 | AC | 90 ms
71,416 KB |
testcase_38 | AC | 91 ms
71,652 KB |
testcase_39 | AC | 92 ms
71,620 KB |
ソースコード
#https://yukicoder.me/problems/no/654 #TLEしてるけどアルゴリズムは合ってるはず import sys sys.setrecursionlimit(10**7) from collections import deque class Edmond_karp: def __init__(self,V): self.v = V self.edges = [[] for _ in range(V)] #隣接リスト def addEdge(self,fr,to,cap): forward = [to,cap,len(self.edges[to])] #行き先、capasity,逆向きの辺のindex backward = [fr,0,len(self.edges[fr])] #逆向きの辺 self.edges[fr].append(forward) self.edges[to].append(backward) def bfs(self,s,t): #tはdestination,fは追加できる最大のフロー量 q = deque([(s,-1,float('inf'),-1)]) #vertex,parent,flow,rev_idx parent = [-1]*self.v revs = [-1]*self.v self.used[s] = 1 parent[s] = -1 revs[s] = -1 #sからでてる逆向きの辺は存在しないので-1でok aug_flow = 0 #sからtまでの最短距離を計算する while len(q) > 0: v,p,f,rev = q.popleft() if v == t: #終点に達したら aug_flow = f break for e in self.edges[v]: w,cap,rev_idx = e #revは反対の辺の情報 if cap and not self.used[w]: q.append((w,v,min(f,cap),rev_idx)) self.used[w] = 1 parent[w] = v revs[w] = rev_idx #wの逆向きの辺のindex # 最短経路のフロー数だけ遡る if aug_flow: #最大値が0じゃなかったら v,p,rev = t,parent[t],revs[t] while p != -1: rev_e = self.edges[v][rev] #tからのreversed edge e = self.edges[p][rev_e[2]] #vじゃだめ。index入れないと e[1] -= aug_flow rev_e[1] += aug_flow v,p,rev = p,parent[p],revs[p] return aug_flow def flow(self,s,t): flow = 0 f = INF = float('inf') v = self.v while f: #この操作回数はO(VE)らしい。 self.used = [0]*v #used初期化 f = self.bfs(s,t) #計算量はO(E) fordfulkersonと一緒 flow += f return flow N,M,d = map(int,input().split()) #(u,pi)→(v,qi)にcapacityがwiの辺を設定 #(u,pi)→(u,pi+1)には容量無限大の辺を設定(空港で待つことを意味する) #上の方法だと間に合わないから #辺を貼るのは街iに飛行機が到着する時刻だけでいい。 def convert(u,time): return u*maxtime + time_dict[time] INF = float('inf') #dを考慮する。Aに出発しBに到着する飛行機はAに出発し、B+dに到着するとみなすことができる。 events = [] time = set() for _ in range(M): u,v,p,q,w = map(int,input().split()) #このqは1日の終わりを超えることはない。 u -= 1 v -= 1 q += d #(u,p)→(v,q+d)へcapacityがwの辺 events.append((u,v,p,q,w)) time.add(p) time.add(q) time = sorted(list(time)) maxtime = len(time) time_dict = {t:i for i,t in enumerate(time)} ff = Edmond_karp(maxtime*N) wait = [[] for _ in range(N)] for u,v,p,q,w in events: ff.addEdge(convert(u,p),convert(v,q),w) wait[u].append(p) wait[v].append(q) for i in range(N): wait[i].sort() for j in range(len(wait[i])-1): t1 = wait[i][j] t2 = wait[i][j+1] ff.addEdge(convert(i,t1),convert(i,t2),INF) print(ff.flow(convert(0,wait[0][0]),convert(N-1,wait[N-1][-1])))