結果
問題 | No.898 tri-βutree |
ユーザー | OKCH3COOH |
提出日時 | 2019-10-26 22:12:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,029 ms / 4,000 ms |
コード長 | 2,362 bytes |
コンパイル時間 | 580 ms |
コンパイル使用メモリ | 86,796 KB |
実行使用メモリ | 167,456 KB |
最終ジャッジ日時 | 2023-08-08 16:29:39 |
合計ジャッジ時間 | 49,253 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 579 ms
137,788 KB |
testcase_01 | AC | 92 ms
71,708 KB |
testcase_02 | AC | 106 ms
77,300 KB |
testcase_03 | AC | 109 ms
76,928 KB |
testcase_04 | AC | 110 ms
77,212 KB |
testcase_05 | AC | 106 ms
77,324 KB |
testcase_06 | AC | 104 ms
77,044 KB |
testcase_07 | AC | 2,754 ms
160,260 KB |
testcase_08 | AC | 2,964 ms
163,612 KB |
testcase_09 | AC | 3,029 ms
161,336 KB |
testcase_10 | AC | 3,012 ms
161,912 KB |
testcase_11 | AC | 2,952 ms
163,000 KB |
testcase_12 | AC | 2,815 ms
162,700 KB |
testcase_13 | AC | 2,757 ms
167,456 KB |
testcase_14 | AC | 3,015 ms
166,964 KB |
testcase_15 | AC | 2,955 ms
157,796 KB |
testcase_16 | AC | 2,868 ms
160,860 KB |
testcase_17 | AC | 2,833 ms
163,076 KB |
testcase_18 | AC | 2,991 ms
162,856 KB |
testcase_19 | AC | 2,992 ms
160,528 KB |
testcase_20 | AC | 2,969 ms
163,120 KB |
testcase_21 | AC | 3,001 ms
165,128 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')