結果

問題 No.1950 片道きゃっちぼーる
コンテスト
ユーザー gr1msl3y
提出日時 2022-05-22 23:11:25
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,021 bytes
コンパイル時間 312 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 233,276 KB
最終ジャッジ日時 2024-09-20 12:57:20
合計ジャッジ時間 13,358 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 17 WA * 6
権限があれば一括ダウンロードができます

ソースコード

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