PreVOI 2023 - Ninh Bình - Police

Xem dạng PDF

Gửi bài giải

Điểm: 70,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 1G
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, PyPy, Python, Scratch

Trong 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

Hãy đọc nội quy trước khi bình luận.



  • 0
    legiahuy22334455  đã bình luận lúc 11, Tháng 8, 2026, 8:46

    https://ideone.com/AvizMS mọi người cho em hỏi sao code em TLE vậy ạ