Có \(N\) thành phố ở Indonesia, được đánh số từ \(0\) đến \(N-1\). Ngoài ra, còn có \(M\) con đường hai chiều, được đánh số từ \(0\) đến \(M-1\). Mỗi con đường nối hai thành phố khác nhau. Con đường thứ \(i\) kết nối thành phố \(U[i]\) với thành phố \(V[i]\) và tiêu thụ \(W[i]\) đơn vị xăng khi đi qua bằng ô tô. Các thành phố được kết nối với nhau sao cho có thể đi lại giữa bất kỳ cặp thành phố nào thông qua các con đường này.

Trong mỗi ngày của \(Q\) ngày tiếp theo, một cặp thành phố muốn thiết lập mối quan hệ chính trị. Cụ thể, vào ngày thứ \(j\), thành phố \(X[j]\) muốn thiết lập mối quan hệ chính trị với thành phố \(Y[j]\). Để thực hiện điều này, thành phố \(X[j]\) sẽ cử một người đại diện đi đến thành phố \(Y[j]\) bằng ô tô. Tương tự, thành phố \(Y[j]\) cũng sẽ cử một người đại diện đi đến thành phố \(X[j]\) bằng ô tô.

Để tránh ùn tắc, hai ô tô không được gặp nhau vào bất kỳ thời điểm nào. Cụ thể, hai ô tô không được ở trong cùng một thành phố vào cùng một thời điểm. Hai ô tô cũng không được đi trên cùng một con đường theo hai hướng ngược nhau vào cùng một thời điểm. Hơn nữa, khi ô tô đi trên một con đường thì phải đi hết con đường và đến thành phố đích; nói cách khác, ô tô không được phép quay đầu ở giữa đường. Tuy nhiên, ô tô được phép đến cùng một thành phố hoặc đi trên cùng một con đường nhiều hơn một lần. Ô tô cũng có thể chờ ở bất kỳ thành phố nào vào bất kỳ thời điểm nào.

Vì ô tô có dung tích bình nhiên liệu lớn sẽ đắt tiền, hai thành phố muốn chọn tuyến đường cho hai ô tô sao cho dung tích bình nhiên liệu lớn nhất của hai ô tô là nhỏ nhất. Ở mỗi thành phố đều có trạm xăng với nguồn cung cấp xăng vô hạn, do đó dung tích bình nhiên liệu mà một ô tô cần bằng mức tiêu thụ xăng lớn nhất trong tất cả các con đường mà ô tô đó đi qua.

Chi tiết cài đặt

Bạn phải cài đặt hai hàm có chữ ký C++ chính xác như sau:

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W);

int getMinimumFuelCapacity(int X, int Y);

Hàm init

Hàm init được trình chấm gọi đúng một lần trước mọi lời gọi getMinimumFuelCapacity.

• N: số lượng thành phố.
• M: số lượng con đường.
• U: mảng gồm \(M\) số nguyên biểu diễn đầu mút thứ nhất của các con đường.
• V: mảng gồm \(M\) số nguyên biểu diễn đầu mút thứ hai của các con đường.
• W: mảng gồm \(M\) số nguyên biểu diễn mức tiêu thụ xăng của các con đường.
• Hàm không trả về giá trị.

Hàm getMinimumFuelCapacity

Hàm getMinimumFuelCapacity được trình chấm gọi đúng \(Q\) lần.

• X: thành phố thứ nhất.
• Y: thành phố thứ hai.
• Hàm phải trả về một số nguyên biểu diễn giá trị nhỏ nhất có thể của dung tích bình nhiên liệu lớn nhất trong hai ô tô, sao cho một người đại diện từ thành phố \(X\) có thể đến thành phố \(Y\) và một người đại diện từ thành phố \(Y\) có thể đến thành phố \(X\) theo các quy tắc đã nêu; trả về \(-1\) nếu không tồn tại cách thực hiện.

Ví dụ

5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1

3
10
4

Trong ví dụ này, \(N=5\), \(M=6\), \(U=[0,0,1,1,1,2]\), \(V=[1,2,2,3,4,3]\), \(W=[4,4,1,2,10,3]\), \(Q=3\), \(X=[1,2,0]\) và \(Y=[2,4,1]\). Ví dụ được minh họa bằng hình dưới đây:

{{asset:apio20swap/example-1.png}}

Trình chấm gọi init(5, 6, [0, 0, 1, 1, 1, 2], [1, 2, 2, 3, 4, 3], [4, 4, 1, 2, 10, 3]). Sau đó, trình chấm gọi:

• getMinimumFuelCapacity(1, 2): đầu tiên, ô tô ở thành phố \(1\) có thể đi đến thành phố \(3\). Tiếp theo, ô tô ở thành phố \(2\) có thể đi đến thành phố \(1\), đồng thời ô tô ở thành phố \(3\) có thể đi đến thành phố \(2\). Do đó, dung tích bình nhiên liệu lớn nhất của hai ô tô là \(3\) đơn vị nhiên liệu, cần để đi từ thành phố \(3\) đến thành phố \(2\). Không có tuyến đường nào cho phép dung tích bình nhiên liệu nhỏ hơn, do đó hàm trả về \(3\).
• getMinimumFuelCapacity(2, 4): bất kỳ ô tô nào đi đến hoặc đi từ thành phố \(4\) đều cần dung tích bình nhiên liệu \(10\) đơn vị, do đó hàm trả về \(10\).
• getMinimumFuelCapacity(0, 1): hàm trả về \(4\).

3 2
0 1 5
0 2 5
1
1 2

-1

Trong ví dụ này, \(N=3\), \(M=2\), \(U=[0,0]\), \(V=[1,2]\), \(W=[5,5]\), \(Q=1\), \(X=[1]\) và \(Y=[2]\). Ví dụ được minh họa bằng hình dưới đây:

{{asset:apio20swap/example-2.png}}

Trình chấm gọi init(3, 2, [0, 0], [1, 2], [5, 5]), sau đó gọi getMinimumFuelCapacity(1, 2). Không thể để ô tô ở thành phố \(1\) đi đến thành phố \(2\) mà không gặp ô tô kia tại một thời điểm nào đó, do đó hàm trả về \(-1\).

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(N-1 \le M \le 200\,000\).
• \(0 \le U[i] < V[i] < N\).
• Có nhiều nhất một con đường giữa mỗi cặp thành phố.
• Có thể đi lại giữa bất kỳ cặp thành phố nào thông qua các con đường.
• \(1 \le W[i] \le 10^9\).
• \(1 \le Q \le 200\,000\).
• \(0 \le X[j] < Y[j] < N\).

Phân nhóm

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu đầu vào theo định dạng sau:

N M
U[0] V[0] W[0]
U[1] V[1] W[1]
.
.
.
U[M-1] V[M-1] W[M-1]
Q
X[0] Y[0]
X[1] Y[1]
.
.
.
X[Q-1] Y[Q-1]

Với mỗi lời gọi getMinimumFuelCapacity, trình chấm mẫu in ra giá trị trả về bởi hàm.

Nguồn

Đề bài chính thức của Ban tổ chức APIO 2020: Swapping Cities.