結果
問題 | No.2642 Don't cut line! |
ユーザー | abap34 |
提出日時 | 2024-02-17 19:47:41 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,216 ms / 4,000 ms |
コード長 | 4,467 bytes |
コンパイル時間 | 290 ms |
コンパイル使用メモリ | 81,700 KB |
実行使用メモリ | 210,588 KB |
最終ジャッジ日時 | 2024-02-20 12:46:18 |
合計ジャッジ時間 | 44,390 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge16 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 43 ms
55,884 KB |
testcase_01 | AC | 1,726 ms
206,356 KB |
testcase_02 | AC | 1,702 ms
206,120 KB |
testcase_03 | AC | 1,741 ms
206,760 KB |
testcase_04 | AC | 1,752 ms
209,296 KB |
testcase_05 | AC | 1,743 ms
207,164 KB |
testcase_06 | AC | 903 ms
123,468 KB |
testcase_07 | AC | 930 ms
121,164 KB |
testcase_08 | AC | 933 ms
122,956 KB |
testcase_09 | AC | 927 ms
122,572 KB |
testcase_10 | AC | 942 ms
121,164 KB |
testcase_11 | AC | 916 ms
123,084 KB |
testcase_12 | AC | 913 ms
123,084 KB |
testcase_13 | AC | 901 ms
122,956 KB |
testcase_14 | AC | 935 ms
122,060 KB |
testcase_15 | AC | 916 ms
123,212 KB |
testcase_16 | AC | 2,216 ms
210,588 KB |
testcase_17 | AC | 1,550 ms
190,768 KB |
testcase_18 | AC | 1,615 ms
195,292 KB |
testcase_19 | AC | 1,238 ms
160,904 KB |
testcase_20 | AC | 981 ms
128,544 KB |
testcase_21 | AC | 1,334 ms
118,064 KB |
testcase_22 | AC | 1,597 ms
168,380 KB |
testcase_23 | AC | 2,001 ms
206,024 KB |
testcase_24 | AC | 1,124 ms
137,596 KB |
testcase_25 | AC | 1,113 ms
132,428 KB |
testcase_26 | AC | 1,107 ms
123,356 KB |
testcase_27 | AC | 1,317 ms
155,124 KB |
testcase_28 | AC | 1,885 ms
190,896 KB |
testcase_29 | AC | 1,123 ms
123,308 KB |
testcase_30 | AC | 1,110 ms
131,800 KB |
testcase_31 | AC | 1,549 ms
172,340 KB |
testcase_32 | AC | 1,098 ms
125,680 KB |
testcase_33 | AC | 45 ms
56,012 KB |
testcase_34 | AC | 43 ms
56,012 KB |
testcase_35 | AC | 42 ms
56,012 KB |
ソースコード
import math from collections import namedtuple INF = 10**16 class UnionFind: def __init__(self, N): self.par = list(range(N)) self.size = [1] * N def root(self, x): if self.par[x] == x: return x else: self.par[x] = self.root(self.par[x]) return self.par[x] def issame(self, x, y): return self.root(x) == self.root(y) def unite(self, x, y): x = self.root(x) y = self.root(y) if x == y: return True if self.size[x] < self.size[y]: self.par[x] = y self.size[y] += self.size[x] else: self.par[y] = x self.size[x] += self.size[y] return True Edge = namedtuple('Edge', ['from_', 'to', 'weight', 'profit']) def reverse(edge): return Edge(edge.to, edge.from_, edge.weight, edge.profit) class Graph: def __init__(self, N): self.edges = [[] for _ in range(N)] def all_edges(self): return [edge for edge_list in self.edges for edge in edge_list] def add(self, edge, has_dir=False): self.edges[edge.from_].append(edge) if not has_dir: self.edges[edge.to].append(reverse(edge)) def as_rooted_tree(graph, root): N = len(graph.edges) tree = Graph(N) stack = [(root, -1)] while stack: v, p = stack.pop() for u in graph.edges[v]: if u.to != p: tree.add(u, has_dir=True) stack.append((u.to, v)) return tree def kruskal(sorted_edges, N): uf = UnionFind(N) graph = Graph(N) cost = 0 profit = -1 for edge in sorted_edges: if not uf.issame(edge.from_, edge.to): uf.unite(edge.from_, edge.to) graph.add(edge) cost += edge.weight profit = max(profit, edge.profit) return graph, cost, profit class LCA: def __init__(self, graph, root=0): V = len(graph.edges) K = math.ceil(math.log2(V)) tree = as_rooted_tree(graph, root) self.parent = [[-1] * V for _ in range(K)] self.dist = [[-1] * V for _ in range(K)] self.depth = [-1] * V self.K = K self.V = V stack = [(root, -1, 0)] while stack: v, p, d = stack.pop() self.depth[v] = d self.parent[0][v] = p for u in tree.edges[v]: if u.to != p: self.dist[0][u.to] = u.weight stack.append((u.to, v, d + 1)) for k in range(K - 1): for v in range(V): if self.parent[k][v] != -1: self.parent[k + 1][v] = self.parent[k][self.parent[k][v]] self.dist[k + 1][v] = max(self.dist[k][v], self.dist[k][self.parent[k][v]]) def max_cost(self, u, v): cost = -INF if self.depth[u] < self.depth[v]: u, v = v, u diff = self.depth[u] - self.depth[v] for k in range(self.K): if (diff >> k) & 1: cost = max(cost, self.dist[k][u]) u = self.parent[k][u] if u == v: return cost for k in range(self.K - 1, -1, -1): if self.parent[k][u] != self.parent[k][v]: cost = max(cost, self.dist[k][u]) cost = max(cost, self.dist[k][v]) u = self.parent[k][u] v = self.parent[k][v] cost = max(cost, self.dist[0][u]) cost = max(cost, self.dist[0][v]) return cost def main(): N, K, C = map(int, input().split()) graph = Graph(N) for _ in range(K): u, v, w, p = map(int, input().split()) u -= 1 v -= 1 edge = Edge(u, v, w, p) graph.add(edge) sorted_edges = graph.all_edges() sorted_edges.sort(key=lambda x: x.weight) mst, C_m, P_m = kruskal(sorted_edges, N) mst_edges_set = set(mst.all_edges()) mst_tree = as_rooted_tree(mst, 0) lca = LCA(mst_tree) sorted_edges.sort(key=lambda x: x.profit, reverse=True) for edge in sorted_edges: P = edge.profit if edge in mst_edges_set: C_add = 0 C_rem = 0 else: u, v = edge.from_, edge.to C_add = edge.weight C_rem = lca.max_cost(u, v) if C_m + C_add - C_rem <= C: print(P) return print(-1) if __name__ == "__main__": main()