#350460 (Python3) No.654 Air E869120

提出ソース

結果

問題	No.654 Air E869120
ユーザー	lan_cable
提出日時	2019-06-07 09:52:10
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	WA
実行時間	-
コード長	7,367 bytes
コンパイル時間	133 ms
コンパイル使用メモリ	13,696 KB
実行使用メモリ	21,280 KB
最終ジャッジ日時	2024-10-04 14:13:52
合計ジャッジ時間	4,433 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	31 ms 18,340 KB
testcase_01	AC	32 ms 11,648 KB
testcase_02	AC	33 ms 11,520 KB
testcase_03	AC	29 ms 11,520 KB
testcase_04	AC	33 ms 11,520 KB
testcase_05	AC	31 ms 11,648 KB
testcase_06	WA	-
testcase_07	AC	31 ms 11,520 KB
testcase_08	AC	30 ms 11,520 KB
testcase_09	AC	31 ms 11,648 KB
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	TLE	-
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	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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
    
    if time_max < p or time_max < q:
        continue
    
    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 True:
    if len(time_seq[s]) == 0 or len(time_seq[t]) == 0:
        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]


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