結果

問題 No.2642 Don't cut line!
ユーザー abap34
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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(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 = 0
profit = -1
for edge in 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 _ in 1:K
u, v, w, p = parse.(Int, split(readline()))
edge = Edge(u, v, w, p)
add!(graph, edge)
end
mst, 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_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()
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0