結果
問題 | No.1615 Double Down |
ユーザー | iaNTU |
提出日時 | 2021-06-22 03:18:05 |
言語 | PyPy3 (7.3.13) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 6,254 bytes |
コンパイル時間 | 417 ms |
コンパイル使用メモリ | 86,764 KB |
実行使用メモリ | 265,588 KB |
最終ジャッジ日時 | 2023-09-24 14:53:01 |
合計ジャッジ時間 | 164,485 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,759 ms
161,852 KB |
testcase_01 | AC | 1,798 ms
161,524 KB |
testcase_02 | AC | 2,193 ms
192,932 KB |
testcase_03 | AC | 2,201 ms
190,384 KB |
testcase_04 | AC | 2,382 ms
205,140 KB |
testcase_05 | AC | 2,314 ms
205,236 KB |
testcase_06 | AC | 2,834 ms
241,440 KB |
testcase_07 | AC | 3,106 ms
249,744 KB |
testcase_08 | AC | 3,040 ms
246,736 KB |
testcase_09 | AC | 8,202 ms
247,648 KB |
testcase_10 | AC | 8,561 ms
238,924 KB |
testcase_11 | AC | 7,749 ms
241,252 KB |
testcase_12 | AC | 4,029 ms
251,556 KB |
testcase_13 | AC | 4,423 ms
255,752 KB |
testcase_14 | AC | 4,094 ms
257,556 KB |
testcase_15 | AC | 3,483 ms
265,588 KB |
testcase_16 | AC | 3,365 ms
260,628 KB |
testcase_17 | AC | 3,313 ms
263,928 KB |
testcase_18 | AC | 8,183 ms
233,424 KB |
testcase_19 | AC | 9,305 ms
238,872 KB |
testcase_20 | AC | 9,123 ms
236,100 KB |
testcase_21 | AC | 9,105 ms
240,028 KB |
testcase_22 | AC | 9,297 ms
245,224 KB |
testcase_23 | TLE | - |
testcase_24 | AC | 8,899 ms
249,412 KB |
testcase_25 | AC | 8,816 ms
243,124 KB |
testcase_26 | AC | 8,297 ms
234,288 KB |
testcase_27 | AC | 583 ms
94,752 KB |
testcase_28 | AC | 597 ms
95,004 KB |
testcase_29 | AC | 687 ms
97,772 KB |
testcase_30 | AC | 672 ms
97,616 KB |
testcase_31 | AC | 702 ms
100,244 KB |
testcase_32 | AC | 751 ms
100,332 KB |
testcase_33 | AC | 898 ms
105,480 KB |
testcase_34 | AC | 884 ms
105,408 KB |
testcase_35 | AC | 981 ms
104,488 KB |
testcase_36 | AC | 201 ms
80,544 KB |
testcase_37 | AC | 204 ms
80,544 KB |
testcase_38 | AC | 222 ms
80,680 KB |
testcase_39 | AC | 233 ms
81,596 KB |
testcase_40 | AC | 219 ms
80,704 KB |
testcase_41 | AC | 217 ms
80,528 KB |
testcase_42 | AC | 251 ms
81,472 KB |
testcase_43 | AC | 262 ms
81,900 KB |
testcase_44 | AC | 249 ms
81,604 KB |
testcase_45 | AC | 101 ms
72,160 KB |
testcase_46 | AC | 102 ms
72,520 KB |
testcase_47 | AC | 103 ms
72,252 KB |
testcase_48 | AC | 102 ms
72,340 KB |
testcase_49 | AC | 100 ms
72,412 KB |
testcase_50 | AC | 100 ms
72,424 KB |
testcase_51 | AC | 100 ms
72,500 KB |
testcase_52 | AC | 103 ms
72,492 KB |
testcase_53 | AC | 101 ms
72,524 KB |
testcase_54 | AC | 102 ms
72,540 KB |
testcase_55 | AC | 102 ms
72,396 KB |
testcase_56 | AC | 103 ms
72,352 KB |
ソースコード
from collections import deque class mf_graph: n=1 g=[[] for i in range(1)] pos=[] def __init__(self,N): self.n=N self.g=[[] for i in range(N)] self.pos = [] def add_edge(self,From,To,cap): assert 0<=From and From<self.n assert 0<=To and To<self.n assert 0<=cap m=len(self.pos) self.pos.append((From,len(self.g[From]))) self.g[From].append({"to":To,"rev":len(self.g[To]),"cap":cap}) self.g[To].append({"to":From,"rev":len(self.g[From])-1,"cap":0}) return m def get_edge(self,i): m=len(self.pos) assert 0<=i and i<m _e=self.g[self.pos[i][0]][self.pos[i][1]] _re=self.g[_e["to"]][_e["rev"]] return {"from":self.pos[i][0], "to":_e["to"], "cap":_e["cap"]+_re["cap"], "flow":_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): m=len(self.pos) assert 0<=i and i<m assert 0<=new_flow and 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 flow(self,s,t,flow_limit=(2**31)-1): assert 0<=s and s<self.n assert 0<=t and t<self.n level=[0 for i in range(self.n)] Iter=[0 for i in range(self.n)] que=deque([]) def bfs(): for i in range(self.n):level[i]=-1 level[s]=0 que=deque([]) que.append(s) while(len(que)>0): 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(func,v,up): if (v==s):return up res=0 level_v=level[v] for i in range(Iter[v],len(self.g[v])): e=self.g[v][i] if (level_v<=level[e["to"]] or self.g[e["to"]][e["rev"]]["cap"]==0):continue d=func(func,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 for i in range(self.n):Iter[i]=0 while(flow<flow_limit): f=dfs(dfs,t,flow_limit-flow) if not(f):break flow+=f return flow def min_cut(self,s): visited=[False for i in range(self.n)] que=deque([]) que.append(s) while(len(que)>0): 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, k, l = map(int, input().split()) x = [0] * l; y = [0] * l; z = [0] * l for i in range(l) : x[i], y[i], z[i] = map(int, input().split()) edges = [[] for i in range(k + 1)] for i in range(l) : edges[z[i]].append(i) alivex = [True] * (n + 1) alivey = [True] * (m + 1) wentx = [False] * (n + 1) wenty = [False] * (m + 1) val = [0] * (k + 1) matchx = [0] * (n + 1) matchy = [0] * (m + 1) S = 0; T = n + m + 1 G = mf_graph(n + m + 2) for j in range(1, n + 1) : G.add_edge(S, j, 1) for j in range(1, m + 1) : G.add_edge(j + n, T, 1) previous_edges = [] for i in range(k, -1, -1) : for j in edges[i] : if alivex[x[j]] and alivey[y[j]] : previous_edges.append(j) G.add_edge(x[j], y[j] + n, 1) gx = [[] for j in range(n + 1)] gy = [[] for j in range(m + 1)] for j in previous_edges : gx[x[j]].append(y[j]) gy[y[j]].append(x[j]) val[i] = G.flow(S, T) for j in range(1, n + 1) : matchx[j] = -1 for j in range(1, m + 1) : matchy[j] = -1 for j in range(1, n + 1) : wentx[j] = False for j in range(1, m + 1) : wenty[j] = False for j in range(1, n + 1) : for e in G.g[j] : if e["to"] != S and e["cap"] == 0 and G.g[e["to"]][e["rev"]]["cap"] == 1 : matchx[j] = e["to"] - n matchy[e["to"] - n] = j qu = [] for j in range(1, n + 1) : if matchx[j] < 0 : wentx[j] = True qu.append(j) while len(qu) : idx = qu.pop() for j in gx[idx] : if not wentx[matchy[j]] : wentx[matchy[j]] = True qu.append(matchy[j]) for j in range(1, n + 1) : if not wentx[j] : alivex[j] = False for j in range(1, m + 1) : if matchy[j] < 0 : wenty[j] = True qu.append(j) while len(qu) : idx = qu.pop() for j in gy[idx] : if not wenty[matchx[j]] : wenty[matchx[j]] = True qu.append(matchx[j]) for j in range(1, m + 1) : if not wenty[j] : alivey[j] = False gsz = [len(G.g[j]) for j in range(0, n + 1)] for j in range(1, n + 1) : if not wentx[j] : for idx in range(gsz[j]) : e = G.g[j][idx] if e["cap"] >= 0 and e["to"] != S and not wenty[e["to"] - n] and matchx[j] != e["to"] - n : G.g[j][idx]["cap"] = 0 G.g[e["to"]][e["rev"]]["cap"] = 0 psz = len(previous_edges) j = 0 while j < psz : idx = previous_edges[j] if not wentx[x[idx]] and not wenty[y[idx]] and matchx[x[idx]] != y[idx] : psz -= 1 previous_edges[j], previous_edges[psz] = previous_edges[psz], previous_edges[j] previous_edges.pop() j -= 1 j += 1 ans = 0 for i in range(0, k + 1) : ans += val[i] << i print(ans)