結果
問題 | No.2642 Don't cut line! |
ユーザー | abap34 |
提出日時 | 2024-02-17 19:44:43 |
言語 | Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 4,467 bytes |
コンパイル時間 | 231 ms |
コンパイル使用メモリ | 13,184 KB |
実行使用メモリ | 129,224 KB |
最終ジャッジ日時 | 2024-09-29 03:33:46 |
合計ジャッジ時間 | 73,666 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 33 ms
11,392 KB |
testcase_01 | TLE | - |
testcase_02 | TLE | - |
testcase_03 | TLE | - |
testcase_04 | TLE | - |
testcase_05 | TLE | - |
testcase_06 | AC | 972 ms
42,372 KB |
testcase_07 | AC | 1,009 ms
42,556 KB |
testcase_08 | AC | 1,003 ms
41,956 KB |
testcase_09 | AC | 1,007 ms
42,648 KB |
testcase_10 | AC | 1,034 ms
42,812 KB |
testcase_11 | AC | 994 ms
42,136 KB |
testcase_12 | AC | 1,029 ms
43,216 KB |
testcase_13 | AC | 988 ms
41,960 KB |
testcase_14 | AC | 1,029 ms
42,740 KB |
testcase_15 | AC | 1,026 ms
43,396 KB |
testcase_16 | TLE | - |
testcase_17 | AC | 3,367 ms
108,708 KB |
testcase_18 | AC | 3,645 ms
116,380 KB |
testcase_19 | AC | 2,491 ms
87,116 KB |
testcase_20 | AC | 1,296 ms
56,228 KB |
testcase_21 | AC | 2,106 ms
52,476 KB |
testcase_22 | AC | 3,003 ms
96,576 KB |
testcase_23 | TLE | - |
testcase_24 | AC | 1,443 ms
66,060 KB |
testcase_25 | AC | 1,373 ms
63,764 KB |
testcase_26 | AC | 1,133 ms
52,664 KB |
testcase_27 | AC | 2,373 ms
84,808 KB |
testcase_28 | AC | 3,775 ms
119,224 KB |
testcase_29 | AC | 1,173 ms
55,572 KB |
testcase_30 | AC | 1,300 ms
60,176 KB |
testcase_31 | AC | 2,948 ms
99,944 KB |
testcase_32 | AC | 1,283 ms
58,420 KB |
testcase_33 | AC | 32 ms
11,264 KB |
testcase_34 | AC | 32 ms
11,392 KB |
testcase_35 | AC | 31 ms
11,392 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()