DSU và cây khung nhỏ nhất
40 bài DSU và cây khung nhỏ nhất, độ khó tăng dần (rating 1100 đến 2400): DSU cơ bản, DSU có trọng số và chẵn lẻ, xử lý offline ngược thời gian, Kruskal, Prim, các biến thể cây khung (cổ chai, cạnh thuộc cây khung, cây khung tốt thứ hai), DSU rollback và cây Kruskal.
Đề bài
40
Mã
Tên
Nhóm
Độ khó
Điểm
% AC
# AC
icpc21_mt_m
Điểm2,00
Câu lạc bộ sinh viên
DSU đếm kích thước nhóm, cộng giai thừa
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
fenceplan
Điểm1,00
Quy hoạch hàng rào
DSU gom nhóm, hình chữ nhật bao mỗi nhóm
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
waterfield
Điểm1,00
Tưới Ruộng
Kruskal trên đồ thị đầy đủ, bỏ cạnh rẻ hơn C
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr10_union
Điểm3,00
Hợp nhóm và kiểm tra
DSU cơ bản: hợp và hỏi cùng nhóm
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr10_sizes
Điểm4,00
Vùng đông dân nhất
DSU theo kích thước, số vùng và vùng lớn nhất
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
th_tst_25_d
Điểm4,00
RING
DSU lưu số đỉnh bậc khác 2, đếm thành phần vòng
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr11_kruskal
Điểm4,00
Xây dựng mạng lưới đường
Kruskal cơ bản, báo không liên thông
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr11_prim
Điểm4,00
Nối mạng các trạm
Prim O(n^2) trên đồ thị đầy đủ Manhattan
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
edgytree
Điểm4,00
Cây có cạnh đen
DSU trên cạnh đỏ, đếm phần bù n^k
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
secretpw
Điểm4,00
Mật khẩu bí mật
DSU dùng 26 chữ cái làm đỉnh trung gian
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
kntourn
Điểm4,00
Giải đấu hiệp sĩ
DSU con trỏ kế tiếp để bỏ qua phần tử đã xoá
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
destarr
Điểm5,00
Phá huỷ mảng
Đảo ngược thời gian: thêm phần tử, DSU tổng đoạn
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr10_parity
Điểm5,00
Lời khai chẵn lẻ
DSU có trọng số chẵn lẻ, mâu thuẫn đầu tiên
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr11_bottle
Điểm5,00
Con đường ít dốc nhất
Đường đi cổ chai nhỏ nhất qua cây DSU của Kruskal
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr11_wells
Điểm5,00
Cấp nước cho các làng
MST với đỉnh ảo nguồn nước
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
voi11_ugnet
Điểm5,00
Nâng cấp mạng
Cây khung lớn nhất, cổ chai mọi cặp đầu cạnh
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr10_offline
Điểm5,00
Cắt cáp mạng
Xoá cạnh offline bằng cách xử lý ngược thời gian
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
harmgraph
Điểm5,00
Đồ thị điều hòa
DSU gom thành phần thành các đoạn liên tiếp
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
lazystud
Điểm5,00
Sinh viên lười (Lazy Student)
Dựng đồ thị theo thứ tự Kruskal cho MST cho trước
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
trpairq
Điểm6,00
Truy vấn cặp đỉnh trên cây
Offline theo ngưỡng, DSU đếm cặp sz_a*sz_b
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
kittens
Điểm6,00
Asya và Mèo Con
DSU kết hợp danh sách liên kết nối đoạn
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
dnai_tst_25_b
Điểm6,00
Nhiệt độ
Kruskal trên lưới, ngưỡng đạt T ô cho mỗi ô
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr11_inmst
Điểm6,00
Đường dây quan trọng
Kruskal theo nhóm trọng số: cạnh mọi/vài/không MST
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
childzoo
Điểm6,00
Vườn Thú Của Bé
Kruskal đếm đóng góp mỗi cạnh cho mọi cặp
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
moonetw
Điểm1,00
Mạng Lưới Bò
MST hình học: chỉ giữ cạnh tới điểm gần mỗi hàng
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
voi14_aznet
Điểm6,00
Mạng truyền thông
MST ràng buộc số cạnh loại A, tính chất trao đổi
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
cowtrv
Điểm1,00
Đi Dự Tiệc COW
Đồ thị hàm, xử lý ngược thời gian bằng DSU
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
buildforest
Điểm7,00
Xây dựng rừng
DSU có trọng số lưu độ sâu so với gốc
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
icpc20_reg_e
Điểm7,00
Xóa cạnh
Kruskal theo nhóm trọng số, đếm lựa chọn thừa
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
portals21
Điểm1,00
Cổng Dịch Chuyển
Mô hình hoá cổng thành đỉnh, MST
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr14_pathmax
Điểm7,00
Cây khung chứa cạnh cho trước
MST chứa cạnh cho trước: bỏ cạnh max trên đường
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
fencedp16
Điểm1,00
Hàng Rào Chia Ô
MST lưới cực lớn, gộp cạnh theo hàng/cột
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
lovetri
Điểm8,00
Tam giác tình yêu
DSU chẵn lẻ, đếm 2^(c-1) cách chia hai nhóm
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
netsafe
Điểm8,00
An toàn mạng
Nhóm cạnh theo XOR, DSU riêng mỗi nhóm
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
hn_tst_26_e
Điểm8,00
Nâng cấp cổng
Cây Kruskal + Euler lá, truy vấn offline
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
envy
Điểm8,00
Cạnh ghen tị
Truy vấn tập cạnh trong MST: DSU rollback theo lớp
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
stspan
Điểm8,00
Cây khung st
Cây khung với ràng buộc bậc của s và t
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
newroadsq
Điểm8,00
Truy Vấn Đường Mới
Cây Kruskal theo ngày + LCA
Chưa phân loại
Tỷ lệ AC
100,0%
AC
2
dsuroll
Điểm8,00
Truy vấn kết nối có hoàn tác
Kết nối động offline: DSU rollback + chia để trị
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0