結果

問題 No.1950 片道きゃっちぼーる
ユーザー roaris
提出日時 2022-05-20 21:45:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,582 ms / 3,000 ms
コード長 2,304 bytes
コンパイル時間 241 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 464,284 KB
最終ジャッジ日時 2024-09-20 07:44:55
合計ジャッジ時間 15,318 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
from collections import *
sys.setrecursionlimit(2*10**5+10)

class Scc:
    def __init__(self, N, G):
        self.N = N
        self.G = G
        self.RG = [[] for _ in range(N)]
        
        for v in range(N):
            for nv in G[v]:
                self.RG[nv].append(v)
    
    def decomp(self):
        order = []
        visited = [False]*self.N
        
        def dfs(v):
            visited[v] = True
            
            for nv in self.G[v]:
                if not visited[nv]:
                    dfs(nv)
            
            order.append(v)
            
        for v in range(self.N):
            if not visited[v]:
                dfs(v)
        
        visited = [False]*self.N
        comp = [-1]*self.N
        label = 0
        
        def rdfs(v, label):
            comp[v] = label
            visited[v] = True
            
            for nv in self.RG[v]:
                if not visited[nv]:
                    rdfs(nv, label)
            
        for v in reversed(order):
            if not visited[v]:
                rdfs(v, label)
                label += 1
        
        return label, comp
    
    def construct(self):
        label, comp = self.decomp()
        belong = [[] for _ in range(label)]
        nG = [set() for _ in range(label)]
        
        for v in range(self.N):
            for nv in self.G[v]:
                if comp[v]!=comp[nv]:
                    nG[comp[v]].add(comp[nv])
            
            belong[comp[v]].append(v)
        
        return belong, nG

N = int(input())
X = list(map(int, input().split()))
d = defaultdict(lambda: -1)

for i in range(N):
    d[X[i]] = i
    
A = list(map(int, input().split()))
G = [[] for _ in range(N)]

for i in range(N):
    if d[X[i]+A[i]]!=-1:
        G[i].append(d[X[i]+A[i]])
    
    if d[X[i]-A[i]]!=-1:
        G[i].append(d[X[i]-A[i]])

scc = Scc(N, G)
belong, nG = scc.construct()
res = [-1]*len(belong)

for i in range(len(belong)):
    for v in belong[i]:
        res[i] = max(res[i], X[v]+A[v])

for v in range(len(belong)-1, -1, -1):
    for nv in nG[v]:
        res[v] = max(res[v], res[nv])

ans = [-1]*N

for i in range(len(belong)):
    for v in belong[i]:
        ans[v] = res[i]-X[v]

for i in range(N):
    print(ans[i])
0