結果

問題 No.1950 片道きゃっちぼーる
ユーザー gr1msl3ygr1msl3y
提出日時 2022-05-22 23:22:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 806 ms / 3,000 ms
コード長 2,040 bytes
コンパイル時間 319 ms
コンパイル使用メモリ 82,496 KB
実行使用メモリ 233,020 KB
最終ジャッジ日時 2024-09-20 12:57:39
合計ジャッジ時間 13,691 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
54,272 KB
testcase_01 AC 42 ms
54,016 KB
testcase_02 AC 42 ms
54,144 KB
testcase_03 AC 559 ms
230,072 KB
testcase_04 AC 609 ms
233,020 KB
testcase_05 AC 42 ms
54,144 KB
testcase_06 AC 496 ms
207,432 KB
testcase_07 AC 473 ms
199,176 KB
testcase_08 AC 543 ms
203,588 KB
testcase_09 AC 535 ms
214,044 KB
testcase_10 AC 606 ms
230,444 KB
testcase_11 AC 551 ms
229,056 KB
testcase_12 AC 578 ms
228,288 KB
testcase_13 AC 687 ms
224,932 KB
testcase_14 AC 576 ms
207,392 KB
testcase_15 AC 806 ms
214,712 KB
testcase_16 AC 516 ms
203,768 KB
testcase_17 AC 42 ms
53,888 KB
testcase_18 AC 616 ms
224,892 KB
testcase_19 AC 796 ms
212,140 KB
testcase_20 AC 517 ms
204,380 KB
testcase_21 AC 584 ms
212,280 KB
testcase_22 AC 577 ms
211,636 KB
権限があれば一括ダウンロードができます

ソースコード

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):
    pos = -10**9
    for v in Y[i]:
        p = A[v]+X[v]
        for u in graph[v]:
            if L[u] == i:
                continue
            p = max(p, ans[u]+X[u])
        pos = max(pos, p)
    for v in Y[i]:
        ans[v] = pos-X[v]

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