結果

問題 No.1950 片道きゃっちぼーる
コンテスト
ユーザー gr1msl3y
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

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