結果

問題 No.1950 片道きゃっちぼーる
ユーザー roarisroaris
提出日時 2022-05-20 21:45:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,763 ms / 3,000 ms
コード長 2,304 bytes
コンパイル時間 188 ms
コンパイル使用メモリ 81,776 KB
実行使用メモリ 463,416 KB
最終ジャッジ日時 2023-10-20 12:13:50
合計ジャッジ時間 18,381 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 44 ms
55,524 KB
testcase_01 AC 45 ms
55,524 KB
testcase_02 AC 45 ms
55,524 KB
testcase_03 AC 1,101 ms
419,964 KB
testcase_04 AC 1,107 ms
241,512 KB
testcase_05 AC 47 ms
55,504 KB
testcase_06 AC 1,068 ms
463,416 KB
testcase_07 AC 511 ms
221,448 KB
testcase_08 AC 458 ms
219,688 KB
testcase_09 AC 875 ms
334,660 KB
testcase_10 AC 547 ms
239,668 KB
testcase_11 AC 528 ms
239,616 KB
testcase_12 AC 538 ms
239,096 KB
testcase_13 AC 624 ms
220,760 KB
testcase_14 AC 482 ms
171,596 KB
testcase_15 AC 1,763 ms
417,996 KB
testcase_16 AC 921 ms
385,484 KB
testcase_17 AC 45 ms
55,500 KB
testcase_18 AC 540 ms
203,060 KB
testcase_19 AC 1,631 ms
378,264 KB
testcase_20 AC 405 ms
195,940 KB
testcase_21 AC 504 ms
176,668 KB
testcase_22 AC 490 ms
172,784 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