結果

問題 No.1950 片道きゃっちぼーる
ユーザー roarisroaris
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
54,400 KB
testcase_01 AC 45 ms
54,016 KB
testcase_02 AC 45 ms
54,144 KB
testcase_03 AC 992 ms
422,024 KB
testcase_04 AC 540 ms
242,088 KB
testcase_05 AC 45 ms
54,528 KB
testcase_06 AC 1,060 ms
464,284 KB
testcase_07 AC 365 ms
222,240 KB
testcase_08 AC 415 ms
220,204 KB
testcase_09 AC 780 ms
327,088 KB
testcase_10 AC 496 ms
240,188 KB
testcase_11 AC 493 ms
240,200 KB
testcase_12 AC 496 ms
239,748 KB
testcase_13 AC 588 ms
221,268 KB
testcase_14 AC 455 ms
171,944 KB
testcase_15 AC 1,582 ms
418,600 KB
testcase_16 AC 929 ms
385,380 KB
testcase_17 AC 42 ms
54,272 KB
testcase_18 AC 496 ms
203,528 KB
testcase_19 AC 1,429 ms
376,880 KB
testcase_20 AC 367 ms
196,404 KB
testcase_21 AC 455 ms
177,424 KB
testcase_22 AC 460 ms
173,588 KB
権限があれば一括ダウンロードができます

ソースコード

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