結果
問題 | No.386 貪欲な領主 |
ユーザー | rpy3cpp |
提出日時 | 2016-07-01 23:24:42 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 3,065 bytes |
コンパイル時間 | 282 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 190,412 KB |
最終ジャッジ日時 | 2024-04-20 20:57:26 |
合計ジャッジ時間 | 7,415 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 43 ms
52,736 KB |
testcase_01 | AC | 43 ms
52,608 KB |
testcase_02 | AC | 48 ms
53,632 KB |
testcase_03 | AC | 44 ms
53,504 KB |
testcase_04 | RE | - |
testcase_05 | AC | 1,353 ms
187,276 KB |
testcase_06 | AC | 1,514 ms
190,412 KB |
testcase_07 | AC | 114 ms
77,568 KB |
testcase_08 | AC | 318 ms
100,472 KB |
testcase_09 | AC | 124 ms
78,336 KB |
testcase_10 | AC | 46 ms
52,736 KB |
testcase_11 | AC | 45 ms
52,608 KB |
testcase_12 | AC | 106 ms
77,056 KB |
testcase_13 | AC | 202 ms
80,892 KB |
testcase_14 | AC | 979 ms
173,564 KB |
testcase_15 | RE | - |
ソースコード
def read_data(): N = int(input()) Es = [[] for i in range(N)] for i in range(N - 1): a, b = map(int, input().split()) Es[a].append(b) Es[b].append(a) Us = [int(input()) for i in range(N)] M = int(input()) moves = [list(map(int, input().split())) for m in range(M)] return N, Es, Us, M, moves class DisjointSet(object): def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * n def union(self, x, y): self._link(self.find_set(x), self.find_set(y)) def _link(self, x, y): if self.rank[x] > self.rank[y]: self.parent[y] = x else: self.parent[x] = y if self.rank[x] == self.rank[y]: self.rank[y] += 1 def find_set(self, x): xp = self.parent[x] if xp != x: self.parent[x] = self.find_set(xp) return self.parent[x] class Tree(object): def __init__(self, N, Es, root, Us): self.n = N self.root = root self.child = [[] for i in range(N)] self.cum_cost = [0 for i in range(N)] self.cost = Us self._set_child(Es) def _set_child(self, Es): que = [self.root] visited = [False] * self.n self.cum_cost[self.root] = self.cost[self.root] while que: v = que.pop() cum_cost_v = self.cum_cost[v] for u in Es[v]: if visited[u]: continue self.child[v].append(u) self.cum_cost[u] = cum_cost_v + self.cost[u] que.append(u) visited[v] = True class LCATarjan(object): def __init__(self, tree): self.n = tree.n self.root = tree.root self.child = tree.child self.ancestor = list(range(self.n)) self.visited = [False] * self.n self.ds = DisjointSet(self.n) self.lca = dict() def find(self, pairs): self._preprocess(pairs) self._LCA(self.root) return self.lca def _preprocess(self, pairs): self.pairs = [[] for node in range(self.n)] for u, v in pairs: self.pairs[u].append(v) self.pairs[v].append(u) def _LCA(self, u): self.ancestor[self.ds.find_set(u)] = u for v in self.child[u]: self._LCA(v) self.ds.union(u, v) self.ancestor[self.ds.find_set(u)] = u self.visited[u] = True for v in self.pairs[u]: if self.visited[v]: self.lca[u, v] = self.ancestor[self.ds.find_set(v)] self.lca[v, u] = self.lca[u, v] def solve(N, Es, Us, M, moves): tree = Tree(N, Es, 0, Us) pairs = [(a, b) for a, b, c in moves] lcat = LCATarjan(tree) lca = lcat.find(pairs) tax = 0 for a, b, c in moves: v = lca[a, b] tax += (tree.cum_cost[a] + tree.cum_cost[b] - tree.cum_cost[v] * 2 + Us[v]) * c return tax pars = read_data() print(solve(*pars))