VOI 24 Bài 2 - Cải thiện đánh giá
Xem dạng PDF
Quốc gia ~Beta~ có ~N~ thành phố được đánh số từ ~1~ đến ~N~. Các thành phố được nối với nhau bởi ~M~ con đường hai chiều, được đánh số từ ~1~ đến ~M~, giữa hai thành phố bất kỳ có tối đa một con đường nối trực tiếp chúng. Con đường hai chiều số ~i~ ~(1 \le i \le M)~ nối trực tiếp giữa hai thành phố phân biệt ~U_i~ và ~V_i~ có độ dài ~W_i~. Một đường đi gồm ~K~ thành phố từ thành phố ~X~ tới thành phố ~Y~ là một chuỗi các thành phố ~P_1, P_2, \dots, P_k,~ sao cho ~P_1 = X~, ~P_k = Y~ và có con đường trực tiếp giữa hai thành phố ~P_i~ và ~P_{i + 1}~ ~(\forall i = 1, 2, \dots, K - 1)~. Ở quốc gia ~Beta~, mọi thành phố đều có đường đi tới thành phố khác. Chi phí di chuyển của một đường đi từ ~X~ tới thành phố ~Y~ là tổng độ dài của các con đường trên đường đi đó. Gọi ~D(X, Y)~ là chi phí di chuyển nhỏ nhất trong số các chi phí di chuyển của các đường đi từ thành phố ~X~ tới thành phố ~Y~. Quy ước ~D(X, X) = 0~ với mọi thành phố ~X~.
Thành phố số ~1~ có một nhà máy đúc khuôn và thành phố số ~2~ có một nhà máy sản xuất mạ tĩnh điện. Một doanh nghiệp muốn chọn một thành phố nào đó để mở một trung tâm chế tạo thép trang trí sử dụng nguyên liệu từ nhà máy đúc khuôn và nhà máy sản xuất mạ tĩnh điện. Thành phố ~Y~ được gọi là tốt hơn hoặc tương đương với thành phố ~X~ khi và chỉ khi ~D(Y, 1) \le D(X, 1)~ và ~D(Y, 2) \le D(X, 2)~. Lưu ý, thành phố ~X~ được xem là tốt hơn hoặc tương đương so với chính nó. Doanh nghiệp tính hạng của thành phố ~X~ là số lượng thành phố ~Y~ tốt hơn hoặc tương đương so với thành phố ~X~. Cụ thể, công thức tính hạng là:
$$R(X) = |\{Y \in \{1, 2, \dots, N\} : D(Y, 1) \le D(X, 1) \text{ và } D(Y, 2) \le D(X, 2) \}|$$
Ngoài ra, doanh nghiệp cũng cam kết với chính quyền địa phương rằng trước khi đặt trung tâm chế tạo thép ở thành phố ~X~ nào đó, họ sẽ cải tạo một con đường nối với thành phố ~X~. Doanh nghiệp đã khảo sát và đứa ra ~P~ phương án. Với Phương án thứ ~j~ ~(1 \le j \le P)~. Với phương án thứ ~j~ ~(1 \le j \le P)~, con đường ~T_j~ nối giữa thành phố ~U_{T_j}~ và ~V_{T_j}~ sẽ được chọn để cải tạo giúp cho độ dài mới ~W_{T_j}'~ bé hơn độ dài ban đầu ~W_{T_j}~. Với mỗi phương án, sau khi cải tạo đường, doanh nghiệp cần tính hạng của thành phố ~U_{T_j}~ và thành phố ~V_{T_j}~. Các phương án là độc lập, nghĩa là các phương án đều chỉ áp dụng lên hiện trạng ban đầu của ~M~ con đường.
~\textbf{Yêu cầu:}~ Với phương án thứ ~j~ ~(1 \le j \le P)~, hãy giúp doanh nghiệp tìm ra hạng của thành phố ~U_{T_j}~ và thành phố ~V_{T_j}~ sau khi cải tạo con đường ~T_j~.
Input
Vào từ file văn bản IMPEVAL.INP:
– Dòng đầu chứa ba số nguyên ~N, M~ và ~P~ lần lượt là số lượng thành phố, số lượng con đường và số lượng phương án ~(2 \le N \le 10^5; 1 \le M, P \le 10^5).~
– Dòng thứ ~i~ trong số ~M~ dòng tiếp theo chứa ba số nguyên ~U_i~, ~V_i~ và ~W_i~ lần lượt là hai thành phố được nối bởi con đường số ~i~ và độ dài của con đường này ~(1 \le U_i, V_i \le N; 1 \le W_i \le 10^9).~
– Dòng thứ ~j~ trong số ~P~ dòng tiếp theo chứa hai số nguyên ~T_j~ và ~W_{T_j}'~ lần lượt là chỉ số con đường được lên phương án cải tạo và độ dài sau khi cải tạo ~(1 \le T_j \le M; 1 \le W_{T_j}' < W_{T_j}).~
Output
Ghi ra file văn bản IMPEVAL.OUT:
– Gồm ~P~ dòng, trong đó dòng thứ ~j~ ghi ra hai số nguyên ~R(U_{T_j})~ và ~R(V_{T_j})~ tương ứng là hạng của thành phố ~U_{T_j}~ và thành phố ~V_{T_j}~ nếu phương án thứ ~j~ được triển khai.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| 1 | ~20\%~ | ~M, P \le 1000~ |
| 2 | ~20\%~ | Mỗi thành phố có nhiều nhất 2 con đường nối với thành phố khác |
| 3 | ~20\%~ | Mọi con đường đều nối với thành phố số 1 hoặc thành phố số 2 |
| 4 | ~20\%~ | ~M = N - 1~ |
| 5 | ~20\%~ | Không có ràng buộc gì thêm |
Sample Input 1
5 6 2
1 5 8
5 2 10
1 3 6
3 2 12
3 4 3
4 2 11
5 2
6 9
Sample Output 1
1 2
1 1
Notes
– Với con đường số ~5~ có độ dài mới bằng ~2~, thành phố số ~3~ có hạng ~1~ do chỉ có duy nhất thành phố số ~3~ tốt hơn hoặc tương đương với thành phố số ~3~, thành phố số ~4~ có hạng ~2~ do có hai thành phố tốt hơn hoặc tương đương với nó là thành phố số ~4~ và thành phố số ~5~.
| X | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| D(X, 1) | 0 | 18 | 6 | 8 | 8 |
| D(X, 2) | 18 | 0 | 12 | 11 | 10 |
– Với con đường số ~6~ có độ dài mới bằng ~9~, thành phố số ~4~ và thành phố ~2~ đều có hạng ~1~.
|
|
Lần lượt minh họa cho truy vấn 1 và 2.
Bình luận
.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.