PreVOI 2023 - Ninh Bình - Police
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Thành phố H được biết đến với cái tên "thiên đường tội phạm" có ~n~ ~(n \le 2 \cdot 10^5)~ giao lộ được nối với nhau bằng ~m~ ~(m \le 2 \cdot 10^5)~ con đường, đảm bảo tồn tại ít nhất một tuyến đường đi giữa ~2~ giao lộ bất kì.
Vào mỗi ngày trong ~q~ ~(q \le 2 \cdot 10^5)~ ngày liên tiếp, cục cảnh sát nhận được một tin báo rằng sẽ có một nhóm tội phạm di chuyển từ ~u~ tới ~v~. Để ngăn chặn nhóm tội phạm, cục cảnh sát có thể điều động duy nhất ~1~ nhóm cảnh sát canh giữ tại ~w~ (khác ~u~ và ~v~) với chi phí là ~a[w]~ sao cho mọi đường đi của tội phạm từ ~u~ tới ~v~ đều phải đi qua ~w~. Hãy tìm chi phí nhỏ nhất để ngăn chặn nhóm tội phạm.
Input
Dòng đầu ghi ~2~ số ~n,m~ là số giao lộ và số con đường trong thành phố ~(n,m \le 2 \cdot 10^5)~
Dòng thứ hai ghi ~n~ số ~a[1], a[2], \dots, a[n]~ là chi phí để điều động cảnh sát tới từng giao lộ ~(a[i] \le 10^9)~.
Sau đó là ~m~ dòng, mỗi dòng ghi ~2~ số ~a,b~, thể hiện có ~1~ con đường nối ~2~ giao lộ ~a~ và ~b~
Dòng tiếp theo ghi số ngày ~q~ có tin báo tội phạm ~(q \le 2 \cdot 10^5)~
Dòng thứ ~i~ trong ~q~ dòng sau ghi ~2~ số ~u,v~ ~(1 \le u,v \le n)~ thể hiện ~1~ nhóm tội phạm di chuyển từ ~u~ tới ~v~ trong ngày thứ ~i~.
Output
In ra ~q~ dòng, dòng thứ ~i~ là chi phí nhỏ nhất để ngăn chặn nhóm tội phạm ở ngày thứ ~i~, hoặc -1 nếu không thể ngăn chặn.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~10\%~ | ~n,m,q \le 300~ |
| 2 | ~30\%~ | ~m=n-1~ |
| 3 | ~60\%~ | Không có giới hạn gì thêm |
Sample Input 1
5 5
4 1 10 7 5
1 2
2 3
3 5
4 3
5 2
5
1 4
3 4
1 3
3 3
5 4
Sample Output 1
1
-1
1
-1
10
Notes
Ngày đầu tiên, ta có thể điều động cảnh sát tới giao lộ ~2~ hoặc ~3~, đáp án là ~\min(a[2],a[3])=1~
Ngày thứ ~2~ và ~4~, ta không thể ngăn chặn nhóm tội phạm.
Ngày thứ ~3~, ta có thể điều động cảnh sát tới giao lộ ~2~, đáp án là ~a[2]=1~
Ngày thứ ~5~, ta có thể điều động cảnh sát tới giao lộ ~3~, đáp án là ~a[3]=10~
Bình luận
https://ideone.com/AvizMS mọi người cho em hỏi sao code em TLE vậy ạ