Đài Loan có mật độ núi cao dày đặc, với hơn 250 đỉnh núi cao hơn 3.000 mét. A-Ming dự định xây dựng mạng lưới robot vận chuyển hàng hóa tự động bằng cáp treo ở Dải núi Trung tâm của Đài Loan để vận chuyển bưu kiện giữa các làng mạc vùng sâu vùng xa.

Trong kế hoạch của A-Ming, mỗi mạng lưới bao gồm \(N\) nút, được đánh số từ \(0\) đến \(N - 1\). Trong số các nút này, chính xác \(K = 6\) nút là các trạm điện và \(N - K\) nút còn lại là các làng. Các nút được kết nối bằng \(N - 1\) dây cáp hai chiều, được đánh số từ \(0\) đến \(N - 2\). Với mỗi \(i\) (\(0 \le i \le N - 2\)), dây cáp \(i\) kết nối các nút \(U[i]\) và \(V[i]\). Mỗi dây cáp kết nối hai nút khác nhau, và mỗi cặp nút được kết nối bởi tối đa một dây cáp. Đảm bảo rằng giữa hai nút bất kỳ đều có thể di chuyển thông qua các dây cáp trong mạng.

Khoảng cách giữa hai nút \(a\) và \(b\) được ký hiệu là \(d(a, b)\) và được định nghĩa như sau:

• Nếu \(a = b\) thì \(d(a, b) = 0\).
• Trái lại, \(d(a, b)\) là số lượng dây cáp tối thiểu cần thiết để di chuyển từ \(a\) đến \(b\).

Ta nói rằng hệ số phân nhánh của mạng ít nhất là \(\delta\) nếu mỗi nút trong mạng được kết nối với chính xác \(1\) hoặc ít nhất \(\delta\) dây cáp. A-Ming biết một số nguyên dương \(B\) mà hệ số phân nhánh của mạng ít nhất là \(B\).

A-Ming đã chuẩn bị 100 loại dây cáp khác nhau, được đánh số từ \(0, 1, \ldots, 99\). Mỗi dây cáp trong mạng được thiết lập từ một trong những loại dây cáp đó.

Các robot sẽ di chuyển dọc theo dây cáp để thực hiện nhiệm vụ giao hàng. A-Ming muốn cài đặt một chương trình điều hướng giúp robot quay trở lại các trạm điện và tự sạc pin. Tuy nhiên, các robot có bộ nhớ cực kỳ hạn chế. Do đó, khi thiết kế chương trình điều hướng, robot chỉ điều hướng dựa trên số lượng trạm điện \(K = 6\), hệ số phân nhánh đảm bảo \(B\) và các loại dây cáp được gắn vào vị trí hiện tại của robot.

Khi một robot muốn di chuyển tại một nút \(u\) là làng được kết nối với hai hoặc nhiều dây cáp, robot trước tiên sẽ quét các dây cáp được kết nối với \(u\) theo một thứ tự bất kỳ. Sau đó, chương trình được cung cấp một danh sách chứa các loại dây cáp theo thứ tự đó. Đối với mỗi dây cáp, chương trình cần đếm số lượng trạm điện sao cho việc đi theo dây cáp đó làm giảm khoảng cách giữa robot và trạm điện.

Cụ thể, gọi \(v_1, \ldots, v_k\) (\(k \ge 2\)) là các nút được kết nối trực tiếp với \(u\) bằng một dây cáp và \(c_i\) (\(1 \le i \le k\)) là loại dây cáp nối nút \(u\) và \(v_i\). Chương trình được cung cấp \(K\), \(B\), và danh sách \(c_1, c_2, \ldots, c_k\). Với mỗi \(i\) (\(1 \le i \le k\)), chương trình phải xác định số lượng trạm điện \(p\) sao cho \(d(v_i, p) < d(u, p)\).

Nhiệm vụ của bạn là xây dựng chiến lược để phân bổ các loại cáp và thiết kế chương trình điều hướng. Điểm số của bài làm của bạn phụ thuộc vào số lượng các loại cáp khác nhau được sử dụng (xem phần Subtask và Chấm điểm để biết thêm chi tiết).

Chi tiết cài đặt

Bạn cần thực hiện hai hàm trong file navigation.h: một hàm để phân bổ loại cáp và một hàm cho chương trình điều hướng của robot. Lưu ý quan trọng: hai hàm này được gọi trong hai tiến trình riêng biệt — hàm construct_network không thể truyền thông tin trực tiếp sang hàm navigate qua biến toàn cục.

Hàm phân bổ loại cáp:

std::vector<int> construct_network(int N, int K, int B,
                                   std::vector<int> U, std::vector<int> V,
                                   std::vector<int> P)

• \(N\): số lượng nút.
• \(K\): số lượng các trạm điện.
• \(B\): hệ số phân nhánh đảm bảo tối thiểu của mạng.
• \(U\), \(V\): các mảng độ dài \(N - 1\) mô tả các sự kết nối của dây cáp.
• \(P\): một mảng độ dài \(K = 6\) mô tả các nút là trạm điện.
• Hàm này được gọi tối đa 10 000 lần cho mỗi trường hợp thử nghiệm.

Hàm này cần trả về một mảng \(T\) độ dài \(N - 1\):

• Một dây cáp thuộc loại \(T[i]\) được sử dụng để kết nối nút \(U[i]\) và \(V[i]\).
• Mỗi phần tử \(T[i]\) phải thoả mãn \(0 \le T[i] < 100\).

Hàm điều hướng của robot:

std::vector<int> navigate(int K, int B, std::vector<int> C)

• \(K\): số lượng các trạm điện.
• \(B\): hệ số phân nhánh đảm bảo tối thiểu của mạng.
• \(C\): danh sách các loại cáp của tất cả dây cáp có kết nối đến nút làng mà kết nối với ít nhất 2 dây cáp, theo thứ tự bất kỳ.
• Đảm bảo rằng độ dài của \(C\) tối thiểu là \(B\).
• Hàm này được gọi tối đa 100 000 lần với mỗi trường hợp thử nghiệm.

Hàm điều hướng không được phụ thuộc vào cấu trúc mạng ban đầu; đặc biệt, hệ thống chấm điểm có thể sắp xếp lại tất cả các lệnh điều hướng trên các mạng được xây dựng khác nhau trong cùng một trường hợp thử nghiệm.

Hàm này cần trả về một mảng \(D\):

• Độ dài mảng \(D\) phải bằng độ dài mảng \(C\).
• \(D[i]\) phải là số lượng các trạm điện mà việc đi theo dây cáp tương ứng với \(C[i]\) làm giảm khoảng cách giữa robot và trạm điện.

Ràng buộc

• \(K = 6\).
• \(K < N \le 100\,000\).
• Tổng các \(N\) qua tất cả lời gọi đến hàm construct_network không vượt quá \(100\,000\) với mỗi trường hợp thử nghiệm.
• \(0 \le U[i] < V[i] < N\) với mỗi \(0 \le i \le N - 2\).
• Luôn có thể di chuyển từ một nút bất kỳ sang một nút bất kỳ khác thông qua các dây cáp.
• \(0 \le P[0] < P[1] < \cdots < P[K-1] < N\).
• Mỗi mảng \(C\) là một hoán vị của danh sách các loại cáp được kết nối với một nút làng nào đó, nút này được kết nối với ít nhất 2 cáp.
• Tổng độ dài của mảng \(C\) qua tất cả các lời gọi đến hàm navigate không vượt quá \(200\,000\) đối với mỗi trường hợp thử nghiệm.

Phân nhóm

• Subtask 1 (6 điểm): \(B = 2\), \(N = 7\).
• Subtask 2 (14 điểm): \(B = 2\), \(U[i] = i\), \(V[i] = i + 1\) với mỗi \(i\) sao cho \(0 \le i < N - 1\) (mạng là một đường thẳng).
• Subtask 3 (20 điểm): \(B = 5\).
• Subtask 4 (20 điểm): \(B = 4\).
• Subtask 5 (40 điểm): \(B = 2\).

Ví dụ

Xét kịch bản với \(N = 9\), \(K = 6\), và \(B = 2\).

Cấu trúc của mạng được cho bởi \(U = [0, 0, 0, 2, 2, 2, 2, 7]\), \(V = [1, 2, 3, 4, 5, 6, 7, 8]\). Các trạm điện là \(P = [1, 3, 4, 5, 6, 7]\).

Lời gọi đến tiến trình đầu tiên:

construct_network(9, 6, 2, [0, 0, 0, 2, 2, 2, 2, 7],
                           [1, 2, 3, 4, 5, 6, 7, 8],
                           [1, 3, 4, 5, 6, 7])

Giả sử A-Ming xây dựng mạng bằng cách trả về:

[0, 10, 1, 2, 3, 4, 5, 5]

Trong mạng này, nút \(0\) (làng) kết nối với nút \(1\) (cáp loại \(0\)), nút \(2\) (cáp loại \(10\)), nút \(3\) (cáp loại \(1\)). Nút \(2\) (làng) kết nối với nút \(0\) (cáp loại \(10\)) và các nút \(4, 5, 6, 7\) (cáp loại \(2, 3, 4, 5\)). Nút \(7\) (trạm điện) kết nối với nút \(8\) (cáp loại \(5\)).

Lời gọi navigate từ nút 0:

navigate(6, 2, [0, 10, 1])

Phân tích khoảng cách:

• Trạm điện nút \(1\): gần nhất với chính nó — \(d(1,1) = 0 < d(0,1) = 1 < d(2,1) = d(3,1) = 2\). Đi theo cáp \((0,1)\) (loại \(0\)) làm giảm khoảng cách đến nút \(1\).
• Trạm điện nút \(3\): gần nhất với chính nó — \(d(3,3) = 0 < d(0,3) = 1 < d(2,3) = 2\). Đi theo cáp \((0,3)\) (loại \(1\)) làm giảm khoảng cách đến nút \(3\).
• Trạm điện nút \(4, 5, 6, 7\): gần nhất với nút \(2\) — \(d(2,u) = 1 < d(0,u) = 2\) với \(u \in \{4,5,6,7\}\). Đi theo cáp \((0,2)\) (loại \(10\)) làm giảm khoảng cách đến cả 4 trạm này.

Số lượng trạm điện có khoảng cách giảm khi đi theo các cáp loại \(0\), \(10\), \(1\) lần lượt là \(1\), \(4\), \(1\). Kết quả trả về:

[1, 4, 1]

Lưu ý: hàm navigate cũng có thể được gọi cho các hoán vị khác của \(C\). Ví dụ, navigate(6, 2, [1, 0, 10]) cũng là một lời gọi hợp lệ cho nút \(0\), và hàm cần trả về [1, 1, 4].

Lời gọi navigate từ nút 2:

navigate(6, 2, [10, 2, 3, 4, 5])

Kết quả trả về:

[2, 1, 1, 1, 1]

Giải thích: Đi theo cáp loại \(10\) (về phía nút \(0\)) làm giảm khoảng cách đến \(2\) trạm điện (nút \(1\) và nút \(3\)). Đi theo mỗi cáp loại \(2, 3, 4, 5\) (về phía các nút \(4, 5, 6, 7\)) đều làm giảm khoảng cách đến đúng \(1\) trạm điện tương ứng.

Trong mạng này, hàm navigate sẽ không bao giờ được gọi cho các nút khác vì: nút \(1, 3, 4, 5, 6, 7\) đều là trạm điện, và nút \(8\) chỉ được nối với duy nhất một dây cáp.

Trong trường hợp thử nghiệm này, các loại dây cáp được sử dụng là \(0, 1, 2, 3, 4, 5\) và \(10\). Do đó, \(S = 11\) được dùng để tính điểm.

Chấm điểm

Trong bất kỳ trường hợp thử nghiệm nào, nếu ít nhất một trong các điều kiện sau xảy ra, điểm số sẽ là \(0\) (thông báo Output isn't correct):

• Giá trị trả về của bất kỳ lệnh gọi nào đến construct_network không hợp lệ.
• Giá trị trả về của bất kỳ lệnh gọi nào đến navigate không chính xác.

Trái lại, gọi \(S\) là số nguyên nhỏ nhất lớn hơn tất cả các số trong mọi mảng \(T\) được trả về từ mỗi lệnh gọi construct_network. Nói cách khác, \(S\) là số nguyên nhỏ nhất sao cho tất cả các mạng được xây dựng chỉ sử dụng các loại cáp \(0, 1, \ldots, S - 1\).

Điểm của bạn cho mỗi subtask phụ thuộc vào \(S\) như sau:

Đặc biệt, trong Subtask 1, 2 và 5, bạn sẽ nhận được toàn bộ số điểm nếu \(S \le 5\), và trong Subtask 3 và 4, bạn sẽ nhận được toàn bộ số điểm nếu \(S \le 4\).