結果
| 問題 | No.654 Air E869120 |
| ユーザー |
 lan_cable
|
| 提出日時 | 2019-06-07 10:17:38 |
| 言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
| 結果 |
WA
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 7,963 bytes |
| コンパイル時間 | 93 ms |
| コンパイル使用メモリ | 13,696 KB |
| 実行使用メモリ | 14,592 KB |
| 最終ジャッジ日時 | 2024-04-15 04:18:47 |
| 合計ジャッジ時間 | 6,679 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
| testcase_36 | WA | - |
| testcase_37 | WA | - |
| testcase_38 | WA | - |
| testcase_39 | WA | - |
ソースコード
#https://yukicoder.me/problems/no/654
#before start, after all gather edge must be processed in some problems
from collections import deque
inpPh = 6
debug = True
debug = False
if not debug:
inpPh = 0
input1 ='''
2 2 5
1 2 0 25 10
1 2 10 40 5
'''[1:]
input2 ='''
4 5 5
1 2 0 15 40
1 3 5 20 10
2 3 30 40 20
2 4 50 80 20
3 4 50 70 30
'''[1:]
input3 ='''
3 4 5
1 2 0 10 10
1 2 10 20 3
2 3 15 25 2
2 3 5 15 10
'''[1:]
input4 ='''
4 3 5
1 2 0 10 100
2 3 15 31 100
3 4 35 45 100
'''[1:]
input5 ='''
4 40 9
2 3 90 99 43
2 3 12 60 56
1 3 5 9 30
4 3 76 96 88
2 4 76 86 66
1 2 36 91 5
2 1 23 82 87
1 4 66 83 12
1 2 2 33 72
4 1 2 90 30
3 2 32 84 25
4 2 13 99 56
4 3 49 56 94
1 3 29 42 31
1 2 86 88 93
3 4 43 51 28
3 4 5 69 60
3 1 3 4 39
1 4 7 73 99
3 2 31 85 94
1 2 89 94 94
2 1 34 70 62
3 4 39 94 63
4 1 23 30 96
3 4 41 81 29
4 3 57 62 48
3 2 33 54 27
3 1 44 73 44
3 2 50 70 19
4 2 19 36 82
4 2 95 97 94
3 4 20 58 10
1 4 4 97 33
2 3 46 58 58
3 1 0 80 45
4 1 1 76 43
3 2 16 97 9
3 1 13 16 45
2 4 4 16 12
2 3 68 98 12
'''[1:]
output1_2_3_4_5 = '''
15 50 2 0 240
'''
inputXs = [input1, input2, input3, input4, input5, None]
try:
inputA0
except:
inputXs[-1] = inputXs[0]
else:
inputXs[-1] = inputA0
inploc = inpPh - 1 #0,1,2
if debug and inpPh > 0:
#print('selected_input:\n'+inputXs[inploc])
pass
inpX_lst = []
if inpPh > 0:
inpX_lst = inputXs[inploc].splitlines()
if inpPh == 0:
N,M,d = tuple(map(lambda x: int(x), input().split() ) )
else:
N,M,d = tuple( map(lambda x: int(x), inpX_lst.pop(0).split() ) )
V, E = N, M
INF = float('inf')
s, t = 0, V-1
time_seq = [[] for _ in range(N)]
time_max = 10**9
nelist,celist = [],[]
elist = []
nov_cur = V
for i in range(E):
if inpPh == 0:
u,v,p,q,w = tuple(map(lambda x: int(x), input().split() ))
else:
u,v,p,q,w = tuple(map(lambda x: int(x), inpX_lst.pop(0).split() ))
u, v, q = u-1,v-1,q+d
timed_u, timed_v = nov_cur, nov_cur +1
ne = {'id':i,'u':timed_u, 'v':timed_v, 'ouv':(u,v), 'c':w, 'f':0, 'p':p, 'q':q, 'rev':None}
nov_cur += 2
nelist.append(ne)
#test = {'time':p,'prcd':1,'jnt':'u','e':ne}
time_seq[u].append((p,1,'u',ne))
time_seq[v].append((q,0,'v',ne))
#print(ne)
#print(u,v,p,q,w)
for i in range(N):
time_seq[i] = sorted(time_seq[i], key=lambda x: (x[0],x[1]) )
#print('time_seq')
for i in range(N):
break
print(f'#town({i}):')
for e in time_seq[i]:
print(e)
#print()
V = nov_cur
#print(time_seq[s])
while 1>0:
if time_seq[s] == [] or time_seq[t] == []:
print(0)
break
clock0,uv_pri0,junc_ent0,e0 = s_fst = time_seq[s][0]
clock1,uv_pri1,junc_ent1,e1 = t_last = time_seq[t][-1]
from_s = e0[junc_ent0]
to_t = e1[junc_ent1]
ne_s = {'id':len(nelist)+0, 'u':s, 'v':from_s, 'ouv':(s,s), 'c':INF, 'f':0, 'p':None, 'q':None, 'rev':None}
ne_t = {'id':len(nelist)+1, 'u':to_t, 'v':t, 'ouv':(t,t), 'c':INF, 'f':0, 'p':None, 'q':None, 'rev':None}
evt_s = ((-INF,0,'v',ne_s))
evt_t = ((time_max,1,'u',ne_t))
time_seq[s].insert(0,evt_s)
time_seq[t].append(evt_t)
nelist.append(ne_s)
nelist.append(ne_t)
for i in range(N):
while len( time_seq[i] ) > 0 :
break
clock,uv_pri,junc_ent,e = time_seq[i][0]
if junc_ent == 'v':
break
else:
time_seq[i].pop(0)
while len(time_seq[i]) > 0:
break
clock,uv_pri,junc_ent,e = time_seq[i][-1]
if junc_ent == 'u':
break
else:
time_seq[i].pop(-1)
for j in range(1, len(time_seq[i]) ):
clock0,uv_pri0,junc_ent0,e0 = time_seq[i][j-1]
clock1,uv_pri1,junc_ent1,e1 = time_seq[i][j]
if clock0 == clock1:
e1[junc_ent1] = e0[junc_ent0]
continue
else:
new_u, new_v= e0[junc_ent0] ,e1[junc_ent1]
ne = {'id':len(nelist),'u':new_u, 'v':new_v, 'ouv':(i,i),'c':INF, 'f':0, 'p':None, 'q':None,'rev':None}
nelist.append(ne)
E = len(nelist)
for ne in nelist:
ne_id, u, v, = ne['id'],ne['u'], ne['v']
ne['rev'] = E + ne_id
ouv = (ne['ouv'][1], ne['ouv'][0])
ce = {'id':E + ne_id, 'u':v, 'v':u, 'ouv':ouv, 'c':0, 'f':0, 'p':None, 'q':None, 'w':0, 'rev':ne_id}
celist.append(ce)
elist = nelist + celist
#print('nov_cur',nov_cur)
V = nov_cur
vaelist = [ [] for i in range(V)]
L_list = [ None for _ in range(V)]
dfs_restart = [0 for _ in range(V)]
prev_ee = [None for i in range(E*2)]
for e in elist:
eid,u = e['id'],e['u']
vaelist[u].append(eid)
def output_v():
for i,va in enumerate(vaelist):
print(i,va)
print()
def output_e():
for i,lv in enumerate(L_list):
print(f'i:{i} L:{lv}')
for i,e in enumerate(elist):
print(i,e)
if i==E-1:
print()
print()
#print(f's,t:{s,t} N,M:{N,M} V,E:{V,E}')
#output_v()
#output_e()
#print(vaelist)
def bfs():
global L_list
L_list = [ -1 for _ in range(V)]
L_list[s] = 0
q = deque()
q.append(s)
while q:
u = q.popleft()
#print(vaelist[u])
for loc_e in vaelist[u]:
e = elist[loc_e]
v,c,f = e['v'], e['c'], e['f']
#print(e)
if f < c and L_list[v] == -1:
L_list[v] = L_list[u]+1
q.append(v)
def dfs_rec(u,res_min):
if u== t:
return res_min
for loc_e in vaelist[u]:
e, e_rev = elist[loc_e], elist [(loc_e+E) % (E+E)]
v, c, f = e['v'], e['c'], e['f']
if c-f > 0 and L_list[u] < L_list[v]:
d = dfs_rec(v,min( c-f, res_min))
if d > 0:
e['f'] += d
e_rev['f'] -=d
v, c, f = e['v'], e['c'], e['f']
return d
return 0
def dfs():
stack =[(None,s,INF)]
last_e,res_min_last = None, None
break1 = False
while stack:
came_e, u, res_min = stack.pop(-1)
for i in range(dfs_restart[u], len(vaelist[u])):
loc_e = vaelist[u][i]
e = elist[loc_e]
dfs_restart[u] = i
v, c, f = e['v'], e['c'], e['f']
if f < c and L_list[u] < L_list[v]:
prev_ee[loc_e] = came_e
res_min_next = min( c-f ,res_min)
#print('rmn:',res_min,f,res_min_next)
if v == t:
last_e, res_min_last = loc_e, res_min_next
#print('reached', last_e, res_min_next)
break1 = True
break
stack.append((loc_e,v, res_min_next) )
if break1:
pass
break
if last_e == None:
return 0
else:
cur_e = last_e
while cur_e != None:
e, e_rev = elist[cur_e], elist[ (cur_e + E) % (E+E) ]
e['f'] += res_min_last
e_rev['f'] -= res_min_last
cur_e = prev_ee[cur_e]
return res_min_last
f_sum = 0
while True:
bfs()
if L_list[t] == -1:
break
dfs_restart = [0 for _ in range(V)]
while True:
new_f = dfs()
#new_f = dfs_rec(s,INF)
#output_e()
f_sum += new_f
if new_f == 0:
break
#print('dfs-phase-end')
print(f_sum)
#output_e()
break
print()