結果
| 問題 | No.1615 Double Down |
| ユーザー |
 iaNTU
|
| 提出日時 | 2021-06-23 02:46:21 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 4,923 bytes |
| コンパイル時間 | 205 ms |
| コンパイル使用メモリ | 82,176 KB |
| 実行使用メモリ | 252,792 KB |
| 最終ジャッジ日時 | 2024-07-17 15:42:37 |
| 合計ジャッジ時間 | 49,761 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2,975 ms
168,624 KB |
| testcase_01 | AC | 2,983 ms
164,648 KB |
| testcase_02 | AC | 3,503 ms
207,652 KB |
| testcase_03 | AC | 4,140 ms
209,312 KB |
| testcase_04 | AC | 3,203 ms
197,572 KB |
| testcase_05 | AC | 3,237 ms
192,592 KB |
| testcase_06 | AC | 4,992 ms
247,400 KB |
| testcase_07 | AC | 4,492 ms
246,648 KB |
| testcase_08 | AC | 4,999 ms
244,976 KB |
| testcase_09 | TLE | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
| testcase_54 | -- | - |
| testcase_55 | -- | - |
| testcase_56 | -- | - |
ソースコード
class mf_graph:
def __init__(self, N) :
self.size = N
self.g = [[] for i in range(self.size)]
self.gsz = [0 for i in range(self.size)]
def add_edge(self, u, v, c) :
self.g[u].append((v, self.gsz[v], c))
self.g[v].append((u, self.gsz[u], 0))
self.gsz[u] += 1
self.gsz[v] += 1
def Bfs(self, s, t) :
q = [s]
q_sz = 1
self.went[s] = t
self.Iter[s] = self.dep[s] = 0
while q_sz > 0 :
now = q.pop()
q_sz -= 1
for i in self.g[now] :
if i[2] > 0 and self.went[i[0]] != t :
self.went[i[0]] = t
self.dep[i[0]] = self.dep[now] + 1
self.Iter[i[0]] = 0
q_sz += 1
q.append(i[0])
def Dfs(self, u, t, nv) :
if u == t :
return nv
while self.Iter[u] < self.gsz[u] :
i = self.Iter[u]
if self.g[u][i][2] > 0 and self.dep[self.g[u][i][0]] > self.dep[u] :
if self.Dfs(self.g[u][i][0], t, nv) > 0 :
self.g[u][i] = (self.g[u][i][0], self.g[u][i][1], 0)
self.g[self.g[u][i][0]][self.g[u][i][1]] = (self.g[self.g[u][i][0]][self.g[u][i][1]][0], self.g[self.g[u][i][0]][self.g[u][i][1]][1], 1)
return 1
self.Iter[u] += 1
return 0
def flow(self, s, t) :
self.dep = [0 for i in range(self.size)]
self.went = [0 for i in range(self.size)]
self.Iter = [0 for i in range(self.size)]
cnt = 0; ans = 0; kInf = 1 << 30
while True :
cnt += 1
self.Bfs(s, cnt)
if self.went[s] != self.went[t] :
break
f = 0
while True :
f = self.Dfs(s, t, kInf)
if f > 0 :
ans += f
else :
break
return ans
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 for i in range(n + 1)]
alivey = [True for i in range(m + 1)]
val = [0 for i in range(k + 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 = []
qu = []
qu_sz = 0
ans = 0
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])
ans += G.flow(S, T) << i
wentx = [False for i in range(n + 1)]
wenty = [False for i in range(m + 1)]
matchx = [-1 for i in range(n + 1)]
matchy = [-1 for i in range(m + 1)]
for j in range(1, n + 1) :
for e in G.g[j] :
if e[0] != S and e[2] == 0 and G.g[e[0]][e[1]][2] == 1 :
matchx[j] = e[0] - n
matchy[e[0] - n] = j
for j in range(1, n + 1) :
if matchx[j] < 0 :
wentx[j] = True
qu_sz += 1
qu.append(j)
while qu_sz > 0 :
idx = qu.pop()
qu_sz -= 1
for j in gx[idx] :
if not wentx[matchy[j]] :
wentx[matchy[j]] = True
qu_sz += 1
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_sz += 1
qu.append(j)
while qu_sz > 0 :
idx = qu.pop()
qu_sz -= 1
for j in gy[idx] :
if not wenty[matchx[j]] :
wenty[matchx[j]] = True
qu_sz += 1
qu.append(matchx[j])
for j in range(1, m + 1) :
if not wenty[j] :
alivey[j] = False
for j in range(1, n + 1) :
if not wentx[j] :
for idx in range(G.gsz[j]) :
e = G.g[j][idx]
if e[2] >= 0 and e[0] != S and not wenty[e[0] - n] and matchx[j] != e[0] - n :
G.g[j][idx] = (G.g[j][idx][0], G.g[j][idx][1], 0)
G.g[e[0]][e[1]] = (G.g[e[0]][e[1]][0], G.g[e[0]][e[1]][1], 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
print(ans)