結果
問題 | No.2642 Don't cut line! |
ユーザー |
![]() |
提出日時 | 2024-02-15 01:20:31 |
言語 | Julia (2.11.2) |
結果 |
AC
|
実行時間 | 2,582 ms / 4,000 ms |
コード長 | 4,802 bytes |
コンパイル時間 | 171 ms |
コンパイル使用メモリ | 6,816 KB |
実行使用メモリ | 509,160 KB |
最終ジャッジ日時 | 2024-10-01 17:42:07 |
合計ジャッジ時間 | 73,606 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
const INF = 10^16struct UnionFindpar::Vector{Int}size::Vector{Int}UnionFind(N) = new(collect(1:N), collect(1:N))endfunction root!(uf::UnionFind, x::Int)if uf.par[x] == xreturn xelsereturn uf.par[x] = root!(uf, uf.par[x])endendfunction issame!(uf::UnionFind, x::Int, y::Int)return root!(uf, x) == root!(uf, y)endfunction 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] = yuf.size[y] += uf.size[x]elseuf.par[y] = xuf.size[x] += uf.size[y]endreturn trueendstruct Edgefrom::Intto::Intweight::Intprofit::Intendfunction reverse(edge::Edge)return Edge(edge.to, edge.from, edge.weight, edge.profit)endstruct Graphedges::Vector{Vector{Edge}}function Graph(N)edges = [Vector{Edge}() for _ in 1:N]new(edges)endendfunction all_edges(graph::Graph)::Vector{Edge}return collect(Iterators.flatten(graph.edges))endfunction add!(graph::Graph, edge::Edge; has_dir=false)push!(graph.edges[edge.from], edge)if !has_dirrev_edge = reverse(edge)push!(graph.edges[edge.to], rev_edge)endendfunction as_rooted_tree(graph::Graph, root::Int)::GraphN = length(graph.edges)tree = Graph(N)function dfs(v, p)for u in graph.edges[v]if u.to != padd!(tree, u, has_dir=true)dfs(u.to, v)endendenddfs(root, -1)return treeendfunction kruskal(graph::Graph; by=identity, rev=false)::Tuple{Graph,Int,Int}N = length(graph.edges)edges = sort(all_edges(graph), by=by, rev=rev)uf = UnionFind(length(graph.edges))graph = Graph(N)cost = 0profit = -1for edge in edgesif !issame!(uf, edge.from, edge.to)unite!(uf, edge.from, edge.to)add!(graph, edge)cost += edge.weightprofit = max(profit, edge.profit)endendreturn graph, cost, profitendstruct LCAparent::Vector{Vector{Int}}dist::Vector{Vector{Int}}depth::Vector{Int}K::IntV::Intfunction 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] = dparent[1][v] = pfor u in tree.edges[v]if u.to != pdist[1][u.to] = u.weightdfs(u.to, v, d + 1)endendenddfs(root, -1, 0)for k in 1:K-1for v in 1:Vif parent[k][v] == -1continueelseparent[k+1][v] = parent[k][parent[k][v]]dist[k+1][v] = max(dist[k][v], dist[k][parent[k][v]])endendendreturn new(parent, dist, depth, K, V)endendfunction max_cost(lca::LCA, u::Int, v::Int)::Intcost = -INFif lca.depth[u] < lca.depth[v]u, v = v, uenddiff = lca.depth[u] - lca.depth[v]for k in 0:lca.K-1if (diff >> k) & 1 == 1cost = max(cost, lca.dist[k+1][u])u = lca.parent[k+1][u]endendif u == vreturn costendfor k in lca.K:-1:1if 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]endendcost = max(cost, lca.dist[1][u])cost = max(cost, lca.dist[1][v])return costendfunction main()N, K, C = parse.(Int, split(readline()))graph = Graph(N)for _ in 1:Ku, v, w, p = parse.(Int, split(readline()))edge = Edge(u, v, w, p)add!(graph, edge)endmst, C_m, P_m = kruskal(graph, by=(x -> x.weight))mst_edges_set = Set{Edge}(all_edges(mst))mst_tree = as_rooted_tree(mst, 1)lca = LCA(mst_tree)cand_edges = all_edges(graph)sort!(cand_edges, by=(x -> x.profit), rev=true)for edge in cand_edgesP = edge.profitif (edge in mst_edges_set)C_add = 0C_rem = 0elseu, v, C_add = edge.from, edge.to, edge.weightC_rem = max_cost(lca, u, v)endif C_m + C_add - C_rem <= Cprintln(P)returnendendprintln(-1)endmain()