結果
問題 | No.898 tri-βutree |
ユーザー | roaris |
提出日時 | 2019-10-05 09:45:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 967 ms / 4,000 ms |
コード長 | 1,727 bytes |
コンパイル時間 | 1,649 ms |
コンパイル使用メモリ | 86,568 KB |
実行使用メモリ | 117,800 KB |
最終ジャッジ日時 | 2023-08-08 16:15:55 |
合計ジャッジ時間 | 18,372 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 351 ms
116,060 KB |
testcase_01 | AC | 90 ms
71,708 KB |
testcase_02 | AC | 97 ms
76,660 KB |
testcase_03 | AC | 97 ms
76,384 KB |
testcase_04 | AC | 102 ms
76,308 KB |
testcase_05 | AC | 97 ms
76,552 KB |
testcase_06 | AC | 97 ms
76,432 KB |
testcase_07 | AC | 932 ms
117,800 KB |
testcase_08 | AC | 919 ms
116,108 KB |
testcase_09 | AC | 894 ms
116,632 KB |
testcase_10 | AC | 924 ms
116,096 KB |
testcase_11 | AC | 917 ms
115,428 KB |
testcase_12 | AC | 967 ms
117,136 KB |
testcase_13 | AC | 924 ms
116,620 KB |
testcase_14 | AC | 965 ms
117,388 KB |
testcase_15 | AC | 914 ms
115,228 KB |
testcase_16 | AC | 917 ms
116,588 KB |
testcase_17 | AC | 915 ms
117,152 KB |
testcase_18 | AC | 928 ms
116,376 KB |
testcase_19 | AC | 924 ms
116,204 KB |
testcase_20 | AC | 911 ms
116,700 KB |
testcase_21 | AC | 940 ms
117,624 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)