結果
問題 | No.898 tri-βutree |
ユーザー | OKCH3COOH |
提出日時 | 2019-10-26 22:12:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,210 ms / 4,000 ms |
コード長 | 2,362 bytes |
コンパイル時間 | 308 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 156,308 KB |
最終ジャッジ日時 | 2024-04-26 09:06:58 |
合計ジャッジ時間 | 49,781 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 585 ms
140,236 KB |
testcase_01 | AC | 46 ms
54,656 KB |
testcase_02 | AC | 68 ms
66,816 KB |
testcase_03 | AC | 67 ms
67,072 KB |
testcase_04 | AC | 67 ms
67,072 KB |
testcase_05 | AC | 69 ms
67,328 KB |
testcase_06 | AC | 66 ms
66,688 KB |
testcase_07 | AC | 2,890 ms
152,840 KB |
testcase_08 | AC | 3,159 ms
155,648 KB |
testcase_09 | AC | 3,073 ms
155,224 KB |
testcase_10 | AC | 3,055 ms
154,704 KB |
testcase_11 | AC | 3,063 ms
152,336 KB |
testcase_12 | AC | 2,899 ms
154,340 KB |
testcase_13 | AC | 2,893 ms
152,172 KB |
testcase_14 | AC | 3,210 ms
156,308 KB |
testcase_15 | AC | 3,116 ms
154,812 KB |
testcase_16 | AC | 3,013 ms
154,084 KB |
testcase_17 | AC | 2,909 ms
152,688 KB |
testcase_18 | AC | 3,150 ms
151,416 KB |
testcase_19 | AC | 3,097 ms
150,624 KB |
testcase_20 | AC | 3,084 ms
154,796 KB |
testcase_21 | AC | 3,143 ms
155,076 KB |
ソースコード
from collections import deque class LCA: def __init__(self, size): self.size = size self.level = (size - 1).bit_length() self.edges = [[] for _ in range(size)] self.depth = [0] * size self.length = [float('inf')] * size self.prev = [None] * size self.kprev = None def addEdge(self, fr, to, cost=1): self.edges[fr].append((to, cost)) self.edges[to].append((fr, cost)) def dfs(self): st = deque([(0, 0)]) self.depth[0] = 0 self.length[0] = 0 while st: now, prev = st.pop() for to, cost in self.edges[now]: if to == prev: continue st.append((to, now)) self.depth[to] = self.depth[now] + 1 self.length[to] = self.length[now] + cost self.prev[to] = now def construct(self): self.dfs() kprev = [self.prev] S = self.prev for _ in range(self.level): T = [0] * self.size for i in range(self.size): if S[i] is None: continue T[i] = S[S[i]] kprev.append(T) S = T self.kprev = kprev def lca(self, u, v): dist = self.depth[v] - self.depth[u] if dist < 0: u, v = v, u dist = -dist for k in range(self.level + 1): if dist & 1: v = self.kprev[k][v] dist //= 2 if u == v: return u for k in range(self.level)[:: -1]: prevU = self.kprev[k][u] prevV = self.kprev[k][v] if prevU != prevV: u = prevU v = prevV return self.kprev[0][u] def dist(self, u, v): return self.length[u] + self.length[v] - self.length[self.lca(u, v)] * 2 N = int(input()) tree = LCA(N) for _ in range(N - 1): fr, to, cost = map(int, input().split()) tree.addEdge(fr, to, cost) tree.construct() Q = int(input()) ans = [] for _ in range(Q): x, y, z = map(int, input().split()) ans.append(min( tree.dist(x, y) + tree.dist(tree.lca(x, y), z), tree.dist(y, z) + tree.dist(tree.lca(y, z), x), tree.dist(z, x) + tree.dist(tree.lca(z, x), y), )) print(*ans, sep='\n')