Thi thử vòng 2 2022 - ngày 1

Tại nước Cộng hòa VOI, có \(N\) thành phố được đánh số từ \(1\) đến \(N\). Các thành phố được kết nối với \(N - 1\) đường hai chiều. Người dân ở Cộng hòa VOI đang đi lại giữa các thành phố bằng những con đường này. Họ có thể đi lại giữa hai thành phố bất kỳ bằng cách đi qua một hoặc một số con đường.

Ông PVH là ứng cử viên tổng thống của Cộng hòa VOI. Tất nhiên, để trở thành tổng thống, ông ta phải thực hiện chiến dịch tranh cử tổng thống. Thư ký của ông đã lên kế hoạch cho \(M\) chiến dịch tranh cử. Trong kế hoạch thứ \(i\), ông PVH sẽ đi từ thành phố \(A_i\) đến thành phố \(B_i\), sử dụng số con đường tối thiểu và phát biểu trước công chúng tại mỗi thành phố trên đường đi (bao gồm thành phố \(A_i\) và thành phố \(B_i\)). Bởi vì thư ký của ông ấy rất giỏi, nên anh ta biết rằng ông PVH sẽ nhận được phiếu \(C_i\) nếu kế hoạch thứ \(i\) được thực hiện. Có thể thực hiện nhiều kế hoạch.

Tuy nhiên, những người ở Cộng hòa VOI rất thiếu kiên nhẫn. Nếu ông PVH phát biểu trước công chúng nhiều lần trong cùng một thành phố, ông sẽ mất sự ủng hộ từ người dân trong Cộng hòa VOI.

Bởi vì ông PVH muốn trở thành tổng thống, ông ấy muốn nhận được càng nhiều phiếu bầu càng tốt. Vì bạn là siêu lập trình viên ở Cộng hòa VOI, ông ấy đã yêu cầu bạn viết một chương trình tính toán số phiếu bầu tối đa mà ông PVH có thể nhận được trong cuộc bầu cử tổng thống với giả định rằng ông ấy sẽ không phát biểu trước công chúng nhiều lần trong cùng một thành phố.

Với \(N\) là số thành phố ở Cộng hòa VOI, thông tin về các con đường, \(M\) là số kế hoạch cho chiến dịch bầu cử và thông tin của từng kế hoạch, hãy viết một chương trình tính toán số phiếu bầu tối đa mà ông PVH có thể nhận được cuộc bầu cử tổng thống.

Input:

• Dòng đầu tiên chứa số nguyên \(N\) \((2 \leq n \leq 10^5)\) là số thành phố tại nước cộng hoà VOI

• \(N - 1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) \((1 \leq u, v \leq N, u \neq v)\) thể hiện con đường nối giữa thành phố \(u\) và thành phố \(v\).

• Dòng tiếp theo chứa số nguyên \(M\) \((1 \leq M \leq 10^5)\) là số kế hoạch tranh cử

• \(M\) dòng tiêp theo, dòng thứ \(i\) chứa ba số nguyên \(A_i, B_i, C_i\) \((1 \leq A_i, B_i \leq N, A_i \neq B_i, 1 \leq C_i \leq 10^4)\) thể hiện kế hoạch thứ \(i\)

Output:

• Gồm một dòng duy nhất là số phiếu tối đa ông PVH có thể nhận được

Scoring:

Bộ test của bài được chia làm các subtask như sau:

• Subtask 1 (10 điểm): \(M \leq 15\)
• Subtask 2 (5 điểm): \(X_i = i,Y_i = i + 1, C_i = 1\)
• Subtask 3 (5 điểm): \(X_i = i,Y_i = i + 1\)
• Subtask 4 (30 điểm): \(C_i = 1\)
• Subtask 5 (10 điểm): \(N \leq 1000, M \leq 1000\)
• Subtask 6 (40 điểm): Không có ràng buộc gì thêm.

Điểm tối đa của bài là \(100\) điểm.

Example

Bạn đang tìm một vị trí trong đất để đặt một con giun, thú cưng của mình, Maximus. Khu vực tìm kiếm là một vùng hình hộp có kích thước \(N \times M \times K\) được chia thành lưới ba chiều gồm các ô hình lập phương. Các ô trong hộp được gắn nhãn \((x, y, z)\), tương ứng với tọa độ của chúng \((1 \leq x \leq N, 1 \leq y \leq M, 1 \leq z \leq K)\). Mỗi ô có độ ẩm nhất định \(H [x, y, z]\) là một số nguyên trong phạm vi \(1 ... 10^9\). Bạn có thể đo độ ẩm của bất kỳ ô nào bằng một cảm biến đặc biệt.

Maximus rất thích những nơi ẩm ướt, vì vậy bạn cần phải đưa nó vào một ô có độ ẩm ước ít nhất cũng bằng các ô lân cận, nếu không, nó sẽ bỏ đi và bạn sẽ khó tìm thấy nó. Nói cách khác, bạn cần đặt Maximus ở ô \((x, y, z)\), sao cho

\(H [x, y, z] \geq max (H [x + 1, y, z], H [x - 1, y, z], H [x, y + 1, z], H [x, y - 1, z], H [x, y, z + 1], H [x, y, z - 1])\)

trong đó một giá trị được coi là 0 khi nó nằm ngoài hộp (vì Maximus muốn ở trong hộp). Tuy nhiên, số lượng ô có thể rất lớn, vì vậy bạn không thể đo độ ẩm của tất cả các ô. Do đó, bạn chỉ có thể do một số lượng ô nhất định

Tương tác

Đầu tiên, bạn cần đọc vào bốn số nguyên \(N, M, K, Q\). Trong đó \(N, M, K\) là kích thước hình hộp và \(Q\) là số truy vấn bạn được hỏi. Sau đó bạn được phép hỏi chương trình các câu như sau:

• ? x y z: chương trình sẽ in ra giá trị \(H[x, y, z]\), lưu ý rằng bạn không được hỏi quá \(Q\) truy vấn này.
• ! x y z: vị trí bạn chọn cho Maximus. Lưu ý rằng bạn chỉ được trả lời một lần duy nhất và chương trình sẽ dừng lại sau đó. Câu trả lời cần thỏa mãn điều kiện đề bài.

Sau mỗi truy vấn bạn cần dùng endl hoặc flush.

Scoring

Bộ test của bài được chia làm các subtask như sau:

• Subtask 1 (10 điểm) \(M = K = 1, N = 1000000, Q = 10000\)
• Subtask 2 (22 điểm) \(M = K = 1, N = 1000000, Q = 35\)
• Subtask 3 (12 điểm) \(K = 1, N = M = 200, Q = 4000\)
• Subtask 4 (19 điểm) \(K = 1, N = M = 1000, Q = 3500\)
• Subtask 5 (14 điểm) \(N = M = K = 100, Q = 10000\)
• Subtask 6 (23 điểm) \(N = M = K = 500, Q = 15000\)

Điểm tối đa của bài là \(100\) điểm. Để đạt được điểm của một subtask, bạn cần làm đúng tất cả test trong subtask đó.

Ví dụ

Bạn có một lưới ô vuông gồm \(R\) hàng và \(C\) cột. Các hàng được đánh số từ \(1\) đến \(R\), các cột được đánh số từ \(1\) đến \(C\). Trên ô nằm ở hàng i và cột \(j\) có \(G[i][j]\) miếng vàng, \(S[i][j]\) miếng bạc và \(B[i][j]\) miếng đồng.

Bạn cần đi từ ô góc trái trên (thuộc hàng \(1\) cột \(1\)) tới ô góc phải dưới (thuộc hàng \(R\) cột \(C\)) của lưới. Đường đi của bạn cần thoả mãn các điều kiện sau:

• Trong mỗi bước, bạn chỉ được đi từ vị trí hiện tại sang một trong bốn ô kề cạnh.
• Tổng số miếng đồng trên các ô bạn đã đi qua không quá \(K\).
• Đường đi của bạn cần có số bước nhỏ nhất có thể.
• Trong số các đường đi có số bước tối thiểu, bạn cần chọn đường đi sao cho (tổng số miếng vàng chia cho tổng số miếng bạc) xét trên các ô đã đi qua là lớn nhất

Input

Dòng đầu tiên chứa 3 số nguyên \(R, C, K\) \((1 \leq R*C \leq 160, 1 \leq K \leq 10^9)\)

• \(R\) dòng tiếp theo, dòng thứ \(i\) chứa \(C\) số nguyên: \(G[i][1] ... G[i][C]\) \((1 \leq G[i][j] \leq 10^6, G[1][1] = G[R][C] = 0)\)

• \(R\) dòng tiếp theo, dòng thứ \(i\) chứa \(C\) số nguyên: \(S[i][1] ... S[i][C]\) \((1 \leq S[i][j] \leq 10^6, S[1][1] = S[R][C] = 0)\)

• \(R\) dòng tiếp theo, dòng thứ \(i\) chứa \(C\) số nguyên: \(B[i][1] ... B[i][C]\) \((1 \leq B[i][j] \leq 10^6, B[1][1] = B[R][C] = 0)\)

Output:

• Gồm 1 dòng, in ra \(-1\) nếu không thể đi từ ô \((1,1)\) đến ô \((R,C)\), ngược lại in ra tỉ lệ vàng chia bạc lớn nhất. Đáp án của bạn được chấp nhận nếu sai khác không quá \(10^{-6}\) so với đáp án của ban giám khảo. Nói cách khác, gọi \(P\) là đáp số của bạn và \(J\) là đáp số của ban giám khảo, bạn sẽ được tính là giải đúng khi và chỉ khi \(\dfrac{|P - J|}{max(1, |J|)} \leq 10^{-6}\).

Scoring

Bộ test của bài được chia làm các subtask như sau:

• Subtask 1 (17 điểm): \(R*C \leq 50\)
• Subtask 2 (17 điểm): \(K \leq 3000\)
• Subtask 3 (29 điểm): \(G, S \leq 7\)
• Subtask 4 (37 điểm): Không có ràng buộc gì thêm.

Điểm tối đa của bài là \(100\) điểm.

Example