結果

問題 No.1950 片道きゃっちぼーる
ユーザー gr1msl3ygr1msl3y
提出日時 2022-05-22 23:22:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 949 ms / 3,000 ms
コード長 2,040 bytes
コンパイル時間 283 ms
コンパイル使用メモリ 81,756 KB
実行使用メモリ 232,684 KB
最終ジャッジ日時 2023-10-20 17:22:26
合計ジャッジ時間 15,362 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 42 ms
55,580 KB
testcase_01 AC 43 ms
55,580 KB
testcase_02 AC 41 ms
55,580 KB
testcase_03 AC 644 ms
228,624 KB
testcase_04 AC 723 ms
232,684 KB
testcase_05 AC 43 ms
55,552 KB
testcase_06 AC 552 ms
206,700 KB
testcase_07 AC 572 ms
198,736 KB
testcase_08 AC 599 ms
203,152 KB
testcase_09 AC 599 ms
213,500 KB
testcase_10 AC 697 ms
229,928 KB
testcase_11 AC 649 ms
228,212 KB
testcase_12 AC 650 ms
227,632 KB
testcase_13 AC 757 ms
224,732 KB
testcase_14 AC 651 ms
206,820 KB
testcase_15 AC 949 ms
214,216 KB
testcase_16 AC 559 ms
203,084 KB
testcase_17 AC 43 ms
55,552 KB
testcase_18 AC 678 ms
224,440 KB
testcase_19 AC 926 ms
211,628 KB
testcase_20 AC 583 ms
204,212 KB
testcase_21 AC 637 ms
212,064 KB
testcase_22 AC 618 ms
211,236 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