結果

問題 No.1833 Subway Planning
ユーザー puznekopuzneko
提出日時 2022-03-04 01:38:29
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,101 bytes
コンパイル時間 1,024 ms
コンパイル使用メモリ 86,936 KB
実行使用メモリ 398,352 KB
最終ジャッジ日時 2023-09-24 21:51:46
合計ジャッジ時間 40,380 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 77 ms
71,308 KB
testcase_01 AC 75 ms
71,232 KB
testcase_02 AC 77 ms
71,216 KB
testcase_03 AC 77 ms
71,216 KB
testcase_04 AC 1,416 ms
325,728 KB
testcase_05 AC 2,231 ms
385,100 KB
testcase_06 AC 1,763 ms
362,360 KB
testcase_07 AC 3,623 ms
371,112 KB
testcase_08 AC 2,926 ms
359,500 KB
testcase_09 TLE -
testcase_10 AC 2,672 ms
384,948 KB
testcase_11 AC 1,563 ms
386,348 KB
testcase_12 AC 1,276 ms
339,912 KB
testcase_13 AC 1,952 ms
368,444 KB
testcase_14 AC 566 ms
208,300 KB
testcase_15 AC 1,374 ms
198,164 KB
testcase_16 AC 576 ms
232,552 KB
testcase_17 AC 1,390 ms
198,772 KB
testcase_18 AC 1,112 ms
199,776 KB
testcase_19 AC 1,446 ms
201,332 KB
testcase_20 AC 1,715 ms
183,176 KB
testcase_21 AC 2,491 ms
301,064 KB
testcase_22 AC 2,216 ms
288,448 KB
testcase_23 AC 74 ms
71,088 KB
testcase_24 AC 73 ms
70,980 KB
testcase_25 AC 74 ms
70,976 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from sys import stdin
n, *indata = map(int, stdin.read().split())
offset = 0
a = []
b = []
c = []
g = [[] for i in range(n+1)]
for i in range(n-1):
    s, t, d  = indata[offset + 3*i]-1,indata[offset + 3*i+1]-1,indata[offset + 3*i+2]
    a.append(s)
    b.append(t)
    c.append(d)
    g[s].append((t,d))
    g[t].append((s,d))

left = -1
right = max(c) + 2
while right - left >= 2:
    mid = (right + left) // 2
    mustin = [0 for i in range(n)]
    start = -1
    for i in range(n-1):
        if c[i] > mid:
            mustin[a[i]] = 1
            mustin[b[i]] = 1
            start = i
    if start == -1:
        right = mid
        continue
    mustvisit = sum(mustin)
    visited = 0
    used = [c[start]]
    check = [False for i in range(n)]
    check[a[start]] = True
    check[b[start]] = True
    que = [(a[start],0,-1)]
    while que:
        now, inout, come = que.pop()
        if inout == 0:
            check[now] = True
            if come != -1:
                used.append(come)
            visited += mustin[now]
            if visited == mustvisit:
                break
            que.append((now,1,come))
            for i, cost in g[now]:
                if not check[i]:
                    que.append((i,0,cost))
        else:
            if mustin[now]:
                break
            else:
                used.pop()
    que = [(b[start],0,-1)]
    while que:
        now, inout, come = que.pop()
        if inout == 0:
            check[now] = True
            if come != -1:
                used.append(come)
            visited += mustin[now]
            if visited == mustvisit:
                break
            que.append((now,1,come))
            for i, cost in g[now]:
                if not check[i]:
                    que.append((i,0,cost))
        else:
            if mustin[now]:
                break
            else:
                used.pop()
    if visited != mustvisit:
        left = mid
    else:
        val = max(used) - min(used)
        if val <= mid:
            right = mid
        else:
            left = mid

print("{}".format(right))
0