Cây: LCA và nhảy nhị phân
40 bài về cây, độ khó tăng dần (rating 1200 đến 2500): độ sâu, kích thước cây con, đường kính, Euler tour, LCA bằng nhảy nhị phân và sparse table, truy vấn khoảng cách, tổ tiên thứ k, mảng hiệu trên cây, đồ thị hàm, gộp nhỏ vào lớn và phân rã trọng tâm.
Đề bài
40
Mã
Tên
Nhóm
Độ khó
Điểm
% AC
# AC
gr12_depth
Điểm3,00
Gốc, cha và độ sâu
BFS/DFS từ gốc: cha và độ sâu
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
treecent
Điểm1,00
Tìm trọng tâm cây
Tìm trọng tâm cây bằng kích thước cây con
Chưa phân loại
Tỷ lệ AC
50,0%
AC
1
planetcyc
Điểm1,00
Chu Trình Hành Tinh
Đồ thị hàm: chu trình và đuôi
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr12_diam
Điểm4,00
Đường kính của cây
Đường kính cây có trọng số, hai lần duyệt
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
compqry1
Điểm1,00
Truy vấn tổ tiên thứ k
Tổ tiên thứ k bằng nhảy nhị phân
Chưa phân loại
Tỷ lệ AC
100,0%
AC
5
planetsq1
Điểm1,00
Hành Tinh (Truy vấn I)
Đi k bước trên đồ thị hàm bằng nhảy nhị phân
Chưa phân loại
Tỷ lệ AC
100,0%
AC
2
gr12_center
Điểm4,00
Đặt trạm phát sóng
Tâm và bán kính cây từ đường kính
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
compqry2
Điểm1,00
Tổ tiên chung thấp nhất (LCA)
LCA bằng nhảy nhị phân
Chưa phân loại
Tỷ lệ AC
57,1%
AC
3
lorenzo
Điểm4,00
Lorenzo Von Matterhorn
LCA trên cây nhị phân ngầm, cộng phí trên đường
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
icpc24_mt_j
Điểm4,00
Truy vấn đường đi
tin/tout kiểm tra đỉnh nằm trên đường đi
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
armycmd
Điểm5,00
Truyền lệnh trong quân đội
Thứ tự preorder: cây con là một đoạn
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr12_far
Điểm5,00
Thành phố xa nhất
Đỉnh xa nhất luôn là đầu mút đường kính
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
pathqry
Điểm1,00
Truy vấn đường đi từ gốc
Euler tour + BIT: tổng đường từ gốc
Chưa phân loại
Tỷ lệ AC
100,0%
AC
3
cntpath
Điểm1,00
Đếm đường đi qua đỉnh
Mảng hiệu trên cây với LCA
Chưa phân loại
Tỷ lệ AC
28,6%
AC
2
lcabin
Điểm5,00
Khoảng cách trên cây có trọng số
Khoảng cách có trọng số qua LCA
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
planetsq2
Điểm1,00
Hành Tinh (Truy vấn II)
Đồ thị hàm: khoảng cách giữa hai đỉnh
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
dhv_tst_26_d
Điểm6,00
Mạng cấp nước
Đại lượng trên đường qua LCA, đếm theo loại khi DFS
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
treequery
Điểm6,00
Truy vấn trên cây
Kiểm tra tập đỉnh nằm cạnh một đường từ gốc
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr14_kthanc
Điểm6,00
Đỉnh thứ k trên đường đi
Đỉnh thứ k trên đường u-v: LCA + tổ tiên thứ k
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
distcolor
Điểm1,00
Số màu phân biệt trong cây con
Gộp nhỏ vào lớn: số màu phân biệt cây con
Chưa phân loại
Tỷ lệ AC
70,0%
AC
6
threepaths
Điểm7,00
Ba đường đi trên cây
Đường kính + BFS đa nguồn chọn đỉnh thứ ba
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
gr14_subsum
Điểm7,00
Tổng cây con với gốc thay đổi
Euler tour, cây con khi đổi gốc
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
lynskyn
Điểm7,00
Xoay vòng hoán vị
Nhảy nhị phân trên mảng next, n-1 bước
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
icpc20_nat_g
Điểm7,00
Cặp lớn nhất
Cặp xa nhất của tập đỉnh qua LCA O(1)
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
eqdistroom
Điểm7,00
Phòng cách đều
Trung điểm đường đi bằng tổ tiên thứ k
Chưa phân loại
Tỷ lệ AC
66,7%
AC
2
watertree
Điểm7,00
Cây nước
Euler tour + segment tree, cây con và đường lên gốc
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
cactus
Điểm7,00
Xương Rồng Đỉnh
Nén chu trình xương rồng thành cây, LCA
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
fixpath1
Điểm1,00
Đường đi độ dài cố định I
Phân rã trọng tâm: đếm đường độ dài k
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
tn_tst_26_c
Điểm7,00
Trại ven hồ
Cây trọng tâm: cập nhật và truy vấn theo bán kính
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
duffarmy
Điểm8,00
Duff trong quân đội
Nhảy nhị phân lưu 10 giá trị nhỏ nhất trên đường
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
runaway
Điểm1,00
Chạy trốn khỏi chuồng
Nhảy nhị phân theo khoảng cách + mảng hiệu
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
yinyang
Điểm1,00
Âm và Dương
Phân rã trọng tâm, đếm đường cân bằng có điểm nghỉ
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
ancchain
Điểm8,00
Dãy tổ tiên trên cây
Nhảy nhị phân trên cây thêm đỉnh online
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
goldxfer
Điểm8,00
Chuyển vàng
Nhảy nhị phân tìm tổ tiên cao nhất còn vàng
Chưa phân loại
Tỷ lệ AC
100,0%
AC
1
lomsat
Điểm8,00
Tổng màu thống trị trên cây
DSU trên cây: tổng màu trội mỗi cây con
Chưa phân loại
Tỷ lệ AC
100,0%
AC
1
gr16_centre
Điểm8,00
Đếm cặp đỉnh gần nhau
Phân rã trọng tâm + hai con trỏ: cặp dist <= K
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
subcolork
Điểm8,00
Truy vấn màu trên cây con
DSU trên cây, đếm màu có tần suất >= k
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0
newbarn
Điểm1,00
Chuồng Trại Mới
Cây thêm đỉnh: khoảng cách xa nhất qua trọng tâm/LCA
Chưa phân loại
Tỷ lệ AC
0,0%
AC
0