#350406 (Python3) No.654 Air E869120

• 問題: No.654 Air E869120
• ユーザー: lan_cable
• 提出日時: 2019-06-06 16:49:16
• 言語: Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
• 結果: WA
• 実行時間: -
• コード長: 7,282 bytes
• コンパイル時間: 95 ms
• コンパイル使用メモリ: 13,696 KB
• 実行使用メモリ: 14,592 KB
• 最終ジャッジ日時: 2024-09-25 11:13:40
• 合計ジャッジ時間: 4,990 ms
• ジャッジサーバーID （参考情報）: judge4 / judge2

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	35 ms; 11,520 KB
testcase_01	AC	35 ms; 11,520 KB
testcase_02	AC	34 ms; 11,520 KB
testcase_03	AC	34 ms; 11,520 KB
testcase_04	AC	34 ms; 11,648 KB
testcase_05	AC	34 ms; 11,520 KB
testcase_06	WA	-
testcase_07	AC	34 ms; 11,520 KB
testcase_08	AC	34 ms; 11,648 KB
testcase_09	AC	34 ms; 11,520 KB
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	AC	365 ms; 14,592 KB
testcase_17	AC	422 ms; 14,464 KB
testcase_18	AC	363 ms; 14,464 KB
testcase_19	AC	378 ms; 14,464 KB
testcase_20	AC	122 ms; 14,464 KB
testcase_21	AC	140 ms; 14,592 KB
testcase_22	AC	73 ms; 14,464 KB
testcase_23	AC	91 ms; 14,336 KB
testcase_24	AC	133 ms; 14,464 KB
testcase_25	AC	67 ms; 14,336 KB
testcase_26	AC	84 ms; 14,336 KB
testcase_27	AC	61 ms; 14,336 KB
testcase_28	AC	76 ms; 14,336 KB
testcase_29	AC	61 ms; 14,464 KB
testcase_30	AC	55 ms; 13,952 KB
testcase_31	AC	56 ms; 13,952 KB
testcase_32	AC	55 ms; 13,952 KB
testcase_33	RE	-
testcase_34	AC	55 ms; 14,080 KB
testcase_35	AC	34 ms; 11,520 KB
testcase_36	AC	33 ms; 11,520 KB
testcase_37	AC	33 ms; 11,520 KB
testcase_38	AC	34 ms; 11,520 KB
testcase_39	AC	35 ms; 11,520 KB

ソースコード

#https://yukicoder.me/problems/no/654
#before start, after all gather edge must be processed in some problems


from collections import deque

inpPh = 5
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)]

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])
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]


ne0 = ne = {'id':len(nelist)+0, 'u':s, 'v':from_s, 'ouv':(s,s), 'c':INF, 'f':0, 'p':None, 'q':None, 'rev':None}
ne1 = ne = {'id':len(nelist)+1, 'u':to_t, 'v':t, 'ouv':(t,t), 'c':INF, 'f':0, 'p':None, 'q':None, 'rev':None}
nelist.append(ne0)
nelist.append(ne1)


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()