Bài 3. Vi khuẩn VIKHUAN (7 điểm)
Một cây rong tảo khổng lồ có cấu tạo như một đồ thị và là một cây với N nút (các nút được đánh số từ
1 đến N) . Tại một số nút của cây, mỗi nút trong số này có một cá thể vi khuẩn đang trú ngụ và không
di chuyển. Vào thời điểm 0, tại một nút P có một lượng độc tố đủ để lan tỏa liên tục không ngừng với
tốc độ 1 đơn vị chiều dài trên một đơn vị thời gian và có thể giết chết mọi vi khuẩn tiếp xúc với nó.
Yêu cầu: cho biết thông tin đầy đủ về cây rong tảo, số lượng vi khuẩn và nơi trú ngụ, vị trí xuất phát
của lượng độc tố (nút P), hãy cho biết thời điểm sớm nhất T mà số lượng vi
khuẩn bị giết vượt quá nửa tổng số vi khuẩn có vào trước thời điểm 0.
Input Output
Input
10
2
Dòng đầu tiên ghi số N (1 ≤ N ≤ 1000)
7
Dòng thứ hai ghi số P (1 ≤ P ≤ N)
1 2 3 5 9 10
Dòng thứ ba ghi danh sách các nút có vi khuẩn đang trú ngụ (danh
4 10 35
sách này có ít nhất 1 nút)
10 5 68
N – 1 dòng cuối cùng ghi độ dài của một đoạn cây rong tảo nối hai
6 4 111
nút kề nhau, mỗi dòng có dạng một bộ ba số nguyên I, J, L cho biết
10 7 31
đoạn nối nút I với nút J có độ dài L ( 1 ≤ L ≤ 30000)
3 2 74
Output:số nguyên T, là thời điểm sớm nhất tìm được.
9 3 67
Ràng buộc: 50% số test ứng với 50% số điểm của bài có N ≤ 200. Thời
3 8 92
gian giới hạn với mỗi test: 01 giây.
4 2 88
1 6 42
Bạn đang xem bài 3. - Đề thi Olympic 4 môn Tin học khối 11 năm 2013