結果
問題 | No.2642 Don't cut line! |
ユーザー | abap34 |
提出日時 | 2024-02-15 02:46:35 |
言語 | Julia (1.10.2) |
結果 |
AC
|
実行時間 | 2,392 ms / 4,000 ms |
コード長 | 4,884 bytes |
コンパイル時間 | 315 ms |
コンパイル使用メモリ | 6,816 KB |
実行使用メモリ | 499,528 KB |
最終ジャッジ日時 | 2024-10-01 17:40:50 |
合計ジャッジ時間 | 68,635 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,323 ms
295,624 KB |
testcase_01 | AC | 2,352 ms
493,480 KB |
testcase_02 | AC | 2,357 ms
496,528 KB |
testcase_03 | AC | 2,392 ms
495,076 KB |
testcase_04 | AC | 2,357 ms
495,556 KB |
testcase_05 | AC | 2,329 ms
499,528 KB |
testcase_06 | AC | 1,457 ms
329,780 KB |
testcase_07 | AC | 1,501 ms
330,512 KB |
testcase_08 | AC | 1,499 ms
329,548 KB |
testcase_09 | AC | 1,508 ms
330,332 KB |
testcase_10 | AC | 1,521 ms
330,556 KB |
testcase_11 | AC | 1,502 ms
329,852 KB |
testcase_12 | AC | 1,473 ms
324,776 KB |
testcase_13 | AC | 1,510 ms
330,064 KB |
testcase_14 | AC | 1,506 ms
329,928 KB |
testcase_15 | AC | 1,490 ms
324,208 KB |
testcase_16 | AC | 2,359 ms
493,820 KB |
testcase_17 | AC | 1,964 ms
460,744 KB |
testcase_18 | AC | 2,039 ms
478,656 KB |
testcase_19 | AC | 1,928 ms
417,772 KB |
testcase_20 | AC | 1,594 ms
335,604 KB |
testcase_21 | AC | 1,572 ms
331,440 KB |
testcase_22 | AC | 1,980 ms
429,144 KB |
testcase_23 | AC | 2,329 ms
489,232 KB |
testcase_24 | AC | 1,668 ms
357,312 KB |
testcase_25 | AC | 1,587 ms
340,804 KB |
testcase_26 | AC | 1,533 ms
330,252 KB |
testcase_27 | AC | 1,828 ms
409,984 KB |
testcase_28 | AC | 2,329 ms
473,832 KB |
testcase_29 | AC | 1,595 ms
335,036 KB |
testcase_30 | AC | 1,586 ms
334,688 KB |
testcase_31 | AC | 2,062 ms
433,640 KB |
testcase_32 | AC | 1,697 ms
333,224 KB |
testcase_33 | AC | 1,328 ms
295,876 KB |
testcase_34 | AC | 1,376 ms
295,472 KB |
testcase_35 | AC | 1,372 ms
295,864 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) function dfs(v, p) for u in graph.edges[v] if u.to != p add!(tree, u, has_dir=true) dfs(u.to, v) end end end dfs(root, -1) 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) function dfs(v, p, d) depth[v] = d parent[1][v] = p for u in tree.edges[v] if u.to != p dist[1][u.to] = u.weight dfs(u.to, v, d + 1) end end end dfs(root, -1, 0) 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 input = parse.(Int, split(readline())) if length(input) == 4 u, v, w, p = input else throw("invalid input: $i, $input") end 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) for edge in sorted_edges 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()