結果
問題 |
No.1950 片道きゃっちぼーる
|
ユーザー |
|
提出日時 | 2022-05-20 22:58:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 677 ms / 3,000 ms |
コード長 | 1,958 bytes |
コンパイル時間 | 187 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 172,208 KB |
最終ジャッジ日時 | 2024-09-20 09:21:51 |
合計ジャッジ時間 | 10,238 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
import sys,random,bisect from collections import deque,defaultdict import heapq from itertools import permutations from math import gcd input = lambda :sys.stdin.readline().rstrip() mi = lambda :map(int,input().split()) li = lambda :list(mi()) INF = 10**17 class UnionFindVerSize(): def __init__(self, N): self._parent = [n for n in range(0, N)] self._size = [1] * N self.group = N def find_root(self, x): if self._parent[x] == x: return x self._parent[x] = self.find_root(self._parent[x]) stack = [x] while self._parent[stack[-1]]!=stack[-1]: stack.append(self._parent[stack[-1]]) for v in stack: self._parent[v] = stack[-1] return self._parent[x] def unite(self, x, y): gx = self.find_root(x) gy = self.find_root(y) if gx == gy: return self.group -= 1 if self._size[gx] < self._size[gy]: self._parent[gx] = gy self._size[gy] += self._size[gx] else: self._parent[gy] = gx self._size[gx] += self._size[gy] def get_size(self, x): return self._size[self.find_root(x)] def is_same_group(self, x, y): return self.find_root(x) == self.find_root(y) N = int(input()) X = li() A = li() dic = {x:i for i,x in enumerate(X)} back = [[] for v in range(N)] for i in range(N): if X[i]+A[i] in dic: j = dic[X[i]+A[i]] back[j].append(i) if X[i]-A[i] in dic: j = dic[X[i]-A[i]] back[j].append(i) ans = [-1 for i in range(N)] idx = [i for i in range(N)] idx.sort(key=lambda i:A[i]+X[i],reverse=True) for i in idx: if ans[i]!=-1: continue stack = [i] ans[i] = A[i]+X[i] while stack: v = stack.pop() for nv in back[v]: if ans[nv]==-1: ans[nv] = A[i]+X[i] stack.append(nv) for i in range(N): print(ans[i]-X[i])