結果
問題 | No.898 tri-βutree |
ユーザー | roaris |
提出日時 | 2019-10-05 09:45:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,009 ms / 4,000 ms |
コード長 | 1,727 bytes |
コンパイル時間 | 403 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 118,824 KB |
最終ジャッジ日時 | 2024-04-26 08:53:22 |
合計ジャッジ時間 | 17,916 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 314 ms
118,824 KB |
testcase_01 | AC | 45 ms
53,888 KB |
testcase_02 | AC | 53 ms
61,952 KB |
testcase_03 | AC | 53 ms
61,312 KB |
testcase_04 | AC | 55 ms
61,568 KB |
testcase_05 | AC | 52 ms
61,440 KB |
testcase_06 | AC | 52 ms
61,952 KB |
testcase_07 | AC | 963 ms
115,680 KB |
testcase_08 | AC | 946 ms
115,208 KB |
testcase_09 | AC | 976 ms
115,400 KB |
testcase_10 | AC | 945 ms
114,656 KB |
testcase_11 | AC | 954 ms
115,136 KB |
testcase_12 | AC | 1,009 ms
115,152 KB |
testcase_13 | AC | 935 ms
113,648 KB |
testcase_14 | AC | 1,006 ms
114,180 KB |
testcase_15 | AC | 975 ms
114,280 KB |
testcase_16 | AC | 983 ms
114,768 KB |
testcase_17 | AC | 956 ms
113,760 KB |
testcase_18 | AC | 954 ms
114,808 KB |
testcase_19 | AC | 952 ms
114,288 KB |
testcase_20 | AC | 977 ms
115,028 KB |
testcase_21 | AC | 983 ms
114,036 KB |
ソースコード
import sys input = sys.stdin.readline from collections import deque def bfs(): depth[0] = 0 queue = deque([]) queue.append(0) while queue: current_node = queue.popleft() for next_node, w in adj_list[current_node]: if depth[next_node] == -1: parent[0][next_node] = current_node depth[next_node] = depth[current_node] + 1 distance[next_node] = distance[current_node] + w queue.append(next_node) def init(): bfs() #initialize depth and parent[0] for k in range(1, log_size): for v in range(N): if parent[k-1][v] == -1: parent[k][v] = -1 else: parent[k][v] = parent[k-1][parent[k-1][v]] def lca(u, v): #return lowest common ancestor when 0 is root node if depth[u] < depth[v]: u, v = v, u for k in range(log_size): if (depth[u]-depth[v])>>k & 1: u = parent[k][u] if u == v: return u for k in range(log_size-1, -1, -1): if parent[k][u] != parent[k][v]: u = parent[k][u] v = parent[k][v] return parent[0][u] def dist(u, v): return distance[u] + distance[v] - 2*distance[lca(u, v)] N = int(input()) adj_list = [[] for _ in range(N)] for _ in range(N-1): ui, vi, wi = map(int, input().split()) adj_list[ui].append((vi, wi)) adj_list[vi].append((ui, wi)) depth = [-1] * N log_size = N.bit_length() parent = [[-1] * N for _ in range(log_size)] distance = [0] * N init() Q = int(input()) for _ in range(Q): xi, yi, zi = map(int, input().split()) print((dist(xi, yi)+dist(yi, zi)+dist(zi, xi)) // 2)