結果

問題 No.1950 片道きゃっちぼーる
ユーザー gr1msl3ygr1msl3y
提出日時 2022-05-22 23:11:25
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,021 bytes
コンパイル時間 167 ms
コンパイル使用メモリ 81,800 KB
実行使用メモリ 232,868 KB
最終ジャッジ日時 2023-10-20 17:22:02
合計ジャッジ時間 13,183 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
55,572 KB
testcase_01 AC 41 ms
55,572 KB
testcase_02 AC 39 ms
55,572 KB
testcase_03 AC 547 ms
229,700 KB
testcase_04 WA -
testcase_05 AC 43 ms
55,580 KB
testcase_06 AC 483 ms
208,296 KB
testcase_07 AC 488 ms
198,732 KB
testcase_08 AC 546 ms
203,084 KB
testcase_09 AC 520 ms
223,916 KB
testcase_10 AC 583 ms
229,928 KB
testcase_11 AC 542 ms
228,244 KB
testcase_12 AC 585 ms
228,676 KB
testcase_13 AC 642 ms
224,744 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 480 ms
204,596 KB
testcase_17 AC 40 ms
55,580 KB
testcase_18 AC 578 ms
224,464 KB
testcase_19 WA -
testcase_20 AC 483 ms
204,084 KB
testcase_21 WA -
testcase_22 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import defaultdict, deque
from bisect import bisect_left
N = int(input())
X = [-10**9]+list(map(int, input().split()))
A = [0]+list(map(int, input().split()))

graph = defaultdict(list)
graph_inv = defaultdict(list)
for i in range(N+1):
    x = X[i]
    a = A[i]
    ind = bisect_left(X, x-a)
    if X[ind] == x-a:
        graph[i].append(ind)
        graph_inv[ind].append(i)
    ind = bisect_left(X, x+a)
    if ind <= N and X[ind] == x+a:
        graph[i].append(ind)
        graph_inv[ind].append(i)


def scc(N, G, RG):
    order = []
    seen = [0]*N
    group = [None]*N

    def dfs(s):
        task = deque([(s, 1), (s, 0)])
        while task:
            v, t = task.pop()
            if t:
                if seen[v] == 2:
                    continue
                seen[v] = 2
                order.append(v)
            else:
                if seen[v]:
                    continue
                seen[v] = 1
                for e in G[v]:
                    if not seen[e]:
                        task.append((e, 1))
                        task.append((e, 0))

    def rdfs(s, col):
        task = deque([s])
        while task:
            v = task.pop()
            if seen[v]:
                continue
            seen[v] = 1
            group[v] = col
            for e in RG[v]:
                if not seen[e]:
                    task.append(e)

    for i in range(N):
        if not seen[i]:
            dfs(i)

    seen = [0]*N
    label = 0
    for s in reversed(order):
        if not seen[s]:
            rdfs(s, label)
            label += 1

    return label, group


n, L = scc(N+1, graph, graph_inv)
Y = [[] for _ in range(n)]
for i in range(N+1):
    Y[L[i]].append(i)

ans = [0]*(N+1)
for i in range(n-1, -1, -1):
    ind = Y[i][-1]
    ans[ind] = A[ind]
    for u in graph[ind]:
        if L[u] == i:
            continue
        ans[ind] = max(ans[ind], X[u]+ans[u]-X[ind])
    for v in Y[i][:-1]:
        ans[v] = X[ind]+ans[ind]-X[v]

print(*ans[1:], sep='\n')
0