結果

問題 No.654 Air E869120
ユーザー lan_cable
提出日時 2019-06-07 10:17:38
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 7,963 bytes
コンパイル時間 103 ms
コンパイル使用メモリ 13,696 KB
実行使用メモリ 14,592 KB
最終ジャッジ日時 2024-10-04 15:19:47
合計ジャッジ時間 7,496 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 5
other WA * 35
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0