結果
問題 | No.2642 Don't cut line! |
ユーザー | abap34 |
提出日時 | 2024-02-17 19:31:00 |
言語 | Julia (1.10.2) |
結果 |
AC
|
実行時間 | 2,339 ms / 4,000 ms |
コード長 | 4,883 bytes |
コンパイル時間 | 139 ms |
コンパイル使用メモリ | 5,120 KB |
実行使用メモリ | 459,252 KB |
最終ジャッジ日時 | 2024-10-01 17:43:53 |
合計ジャッジ時間 | 65,017 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,363 ms
295,164 KB |
testcase_01 | AC | 2,339 ms
458,260 KB |
testcase_02 | AC | 2,257 ms
459,252 KB |
testcase_03 | AC | 2,243 ms
458,660 KB |
testcase_04 | AC | 2,253 ms
458,536 KB |
testcase_05 | AC | 2,196 ms
458,240 KB |
testcase_06 | AC | 1,461 ms
329,052 KB |
testcase_07 | AC | 1,467 ms
322,696 KB |
testcase_08 | AC | 1,458 ms
327,596 KB |
testcase_09 | AC | 1,472 ms
328,052 KB |
testcase_10 | AC | 1,456 ms
322,716 KB |
testcase_11 | AC | 1,470 ms
327,348 KB |
testcase_12 | AC | 1,498 ms
322,620 KB |
testcase_13 | AC | 1,489 ms
327,288 KB |
testcase_14 | AC | 1,509 ms
321,912 KB |
testcase_15 | AC | 1,480 ms
322,528 KB |
testcase_16 | AC | 2,327 ms
458,028 KB |
testcase_17 | AC | 1,849 ms
431,140 KB |
testcase_18 | AC | 1,897 ms
452,996 KB |
testcase_19 | AC | 1,806 ms
396,016 KB |
testcase_20 | AC | 1,532 ms
331,024 KB |
testcase_21 | AC | 1,707 ms
329,388 KB |
testcase_22 | AC | 2,085 ms
404,208 KB |
testcase_23 | AC | 2,191 ms
455,988 KB |
testcase_24 | AC | 1,565 ms
357,280 KB |
testcase_25 | AC | 1,561 ms
338,568 KB |
testcase_26 | AC | 1,518 ms
328,728 KB |
testcase_27 | AC | 1,726 ms
386,068 KB |
testcase_28 | AC | 1,921 ms
448,984 KB |
testcase_29 | AC | 1,568 ms
332,388 KB |
testcase_30 | AC | 1,574 ms
333,924 KB |
testcase_31 | AC | 1,788 ms
409,740 KB |
testcase_32 | AC | 1,566 ms
332,064 KB |
testcase_33 | AC | 1,381 ms
295,420 KB |
testcase_34 | AC | 1,360 ms
296,864 KB |
testcase_35 | AC | 1,385 ms
295,400 KB |
ソースコード
const INF = 10^16 struct UnionFind par::Vector{Int} size::Vector{Int} UnionFind(N) = new(collect(1:N), collect(1:N)) end function root!(uf::UnionFind, x::Int) if uf.par[x] == x return x else return uf.par[x] = root!(uf, uf.par[x]) end end function issame!(uf::UnionFind, x::Int, y::Int) return root!(uf, x) == root!(uf, y) end function unite!(uf::UnionFind, x::Int, y::Int) x = root!(uf, x) y = root!(uf, y) (x == y) && (return true) if (uf.size[x] < uf.size[y]) uf.par[x] = y uf.size[y] += uf.size[x] else uf.par[y] = x uf.size[x] += uf.size[y] end return true end struct Edge from::Int to::Int weight::Int profit::Int end function reverse(edge::Edge) return Edge(edge.to, edge.from, edge.weight, edge.profit) end struct Graph edges::Vector{Vector{Edge}} function Graph(N) edges = [Vector{Edge}() for _ in 1:N] new(edges) end end function all_edges(graph::Graph)::Vector{Edge} return collect(Iterators.flatten(graph.edges)) end function add!(graph::Graph, edge::Edge; has_dir=false) push!(graph.edges[edge.from], edge) if !has_dir rev_edge = reverse(edge) push!(graph.edges[edge.to], rev_edge) end end function as_rooted_tree(graph::Graph, root::Int)::Graph N = length(graph.edges) tree = Graph(N) stack = [(root, -1)] while !isempty(stack) v, p = pop!(stack) for u in graph.edges[v] if u.to != p add!(tree, u, has_dir=true) push!(stack, (u.to, v)) end end end return tree end function kruskal(sorted_edges::Vector{Edge}, N)::Tuple{Graph,Int,Int} uf = UnionFind(N) graph = Graph(N) cost = 0 profit = -1 for edge in sorted_edges if !issame!(uf, edge.from, edge.to) unite!(uf, edge.from, edge.to) add!(graph, edge) cost += edge.weight profit = max(profit, edge.profit) end end return graph, cost, profit end struct LCA parent::Vector{Vector{Int}} dist::Vector{Vector{Int}} depth::Vector{Int} K::Int V::Int function LCA(graph::Graph; root=1) V = length(graph.edges) K = ceil(Int, log2(V)) tree = as_rooted_tree(graph, root) parent = [fill(-1, V) for _ in 1:K] dist = [fill(-1, V) for _ in 1:K] depth = fill(-1, V) stack = [(root, -1, 0)] while !isempty(stack) v, p, d = pop!(stack) depth[v] = d parent[1][v] = p for u in tree.edges[v] if u.to != p dist[1][u.to] = u.weight push!(stack, (u.to, v, d + 1)) end end end for k in 1:K-1 for v in 1:V if parent[k][v] == -1 continue else parent[k+1][v] = parent[k][parent[k][v]] dist[k+1][v] = max(dist[k][v], dist[k][parent[k][v]]) end end end return new(parent, dist, depth, K, V) end end function max_cost(lca::LCA, u::Int, v::Int)::Int cost = -INF if lca.depth[u] < lca.depth[v] u, v = v, u end diff = lca.depth[u] - lca.depth[v] for k in 0:lca.K-1 if (diff >> k) & 1 == 1 cost = max(cost, lca.dist[k+1][u]) u = lca.parent[k+1][u] end end if u == v return cost end for k in lca.K:-1:1 if lca.parent[k][u] != lca.parent[k][v] cost = max(cost, lca.dist[k][u]) cost = max(cost, lca.dist[k][v]) u = lca.parent[k][u] v = lca.parent[k][v] end end cost = max(cost, lca.dist[1][u]) cost = max(cost, lca.dist[1][v]) return cost end function main() N, K, C = parse.(Int, split(readline())) graph = Graph(N) for i in 1:K u, v, w, p = parse.(Int, split(readline())) edge = Edge(u, v, w, p) add!(graph, edge) end sorted_edges = all_edges(graph) sort!(sorted_edges, by=(x -> x.weight), rev=false) mst, C_m, P_m = kruskal(sorted_edges, N) mst_edges_set = Set{Edge}(all_edges(mst)) mst_tree = as_rooted_tree(mst, 1) lca = LCA(mst_tree) sort!(sorted_edges, by=(x -> x.profit), rev=true) i = 0 for edge in sorted_edges i += 1 P = edge.profit if (edge in mst_edges_set) C_add = 0 C_rem = 0 else u, v, C_add = edge.from, edge.to, edge.weight C_rem = max_cost(lca, u, v) end if C_m + C_add - C_rem <= C println(P) return end end println(-1) end main()