3. IOI 2025 — World Map
Ông Pacha, một nhà khảo cổ học người Bolivia, đã phát hiện một tài liệu cổ gần Tiwanaku mô tả thế giới trong thời kỳ Tiwanaku (300-1000 CN). Vào thời điểm đó, có \(N\) quốc gia, được đánh số từ \(1\) đến \(N\).
Trong tài liệu, có một danh sách gồm \(M\) cặp quốc gia kề nhau khác nhau:
Với mỗi \(i\) (\(0 \leq i < M\)), tài liệu nêu rằng quốc gia \(A[i]\) kề với quốc gia \(B[i]\) và ngược lại. Các cặp quốc gia không có trong danh sách thì không kề nhau.
Ông Pacha muốn tạo một bản đồ thế giới sao cho mọi quan hệ kề nhau giữa các quốc gia đúng như trong thời kỳ Tiwanaku. Để làm việc này, trước hết ông chọn một số nguyên dương \(K\). Sau đó, ông vẽ bản đồ dưới dạng một lưới ô vuông kích thước \(K \times K\), với các hàng được đánh số từ \(0\) đến \(K-1\) (từ trên xuống dưới) và các cột được đánh số từ \(0\) đến \(K-1\) (từ trái sang phải).
Ông muốn tô màu mỗi ô của bản đồ bằng một trong \(N\) màu. Các màu được đánh số từ \(1\) đến \(N\), và quốc gia \(j\) (\(1 \leq j \leq N\)) được biểu diễn bởi màu \(j\). Cách tô màu phải thoả mãn tất cả các điều kiện sau:
- Với mỗi \(j\) (\(1 \leq j \leq N\)), có ít nhất một ô có màu \(j\).
- Với mỗi cặp quốc gia kề nhau \((A[i], B[i])\), có ít nhất một cặp ô kề nhau sao cho một ô có màu \(A[i]\) và ô kia có màu \(B[i]\). Hai ô được gọi là kề nhau nếu chúng chia sẻ một cạnh chung.
- Với mỗi cặp ô kề nhau có màu khác nhau, các quốc gia được biểu diễn bởi hai màu này phải kề nhau trong thời kỳ Tiwanaku.
Ví dụ, nếu \(N = 3\), \(M = 2\) và các cặp quốc gia kề nhau là \((1, 2)\) và \((2, 3)\), thì cặp \((1, 3)\) không kề nhau, và bản đồ kích thước \(K = 3\) dưới đây thoả mãn tất cả các điều kiện.
Đặc biệt, một quốc gia không cần phải tạo thành một vùng liên thông trên bản đồ. Trong bản đồ trên, quốc gia \(3\) tạo thành một vùng liên thông, trong khi các quốc gia \(1\) và \(2\) tạo thành các vùng không liên thông.
Nhiệm vụ của bạn là giúp ông Pacha chọn giá trị của \(K\) và tạo một bản đồ. Tài liệu đảm bảo rằng tồn tại một bản đồ như vậy. Vì ông Pacha thích bản đồ nhỏ hơn, trong subtask cuối điểm của bạn phụ thuộc vào giá trị của \(K\), và giá trị \(K\) nhỏ hơn có thể cho điểm cao hơn. Tuy nhiên, không yêu cầu tìm giá trị nhỏ nhất có thể của \(K\).
Chi tiết cài đặt
Bạn cần cài đặt hàm sau:
std::vector<std::vector<int>> create_map(int N, int M,
std::vector<int> A, std::vector<int> B)
- \(N\): số lượng quốc gia.
- \(M\): số lượng cặp quốc gia kề nhau.
- \(A\) và \(B\): hai mảng độ dài \(M\) mô tả các quốc gia kề nhau.
- Hàm này được gọi tối đa \(50\) lần cho mỗi test case.
Hàm trả về một mảng \(C\) biểu diễn bản đồ. Gọi \(K\) là độ dài của \(C\).
- Mỗi phần tử của \(C\) phải là một mảng độ dài \(K\), chứa các số nguyên trong khoảng từ \(1\) đến \(N\).
- \(C[i][j]\) là màu của ô tại hàng \(i\) và cột \(j\) (với mỗi \(i\) và \(j\) thoả mãn \(0 \leq i, j < K\)).
- \(K\) phải nhỏ hơn hoặc bằng \(240\).
Ràng buộc
- \(1 \leq N \leq 40\)
- \(0 \leq M \leq \frac{N \cdot (N-1)}{2}\)
- \(1 \leq A[i] < B[i] \leq N\) với mỗi \(i\) thoả mãn \(0 \leq i < M\).
- Các cặp \((A[0], B[0]), \ldots, (A[M-1], B[M-1])\) là phân biệt.
- Tồn tại ít nhất một bản đồ thoả mãn tất cả các điều kiện.
Phân nhóm
- Subtask 1 (\(5\) điểm): \(M = N - 1\), \(A[i] = i + 1\), \(B[i] = i + 2\) với mỗi \(0 \leq i < M\).
- Subtask 2 (\(10\) điểm): \(M = N - 1\).
- Subtask 3 (\(7\) điểm): \(M = \frac{N \cdot (N-1)}{2}\).
- Subtask 4 (\(8\) điểm): Quốc gia \(1\) kề với tất cả các quốc gia khác. Một số cặp quốc gia khác cũng có thể kề nhau.
- Subtask 5 (\(14\) điểm): \(N \leq 15\).
- Subtask 6 (\(56\) điểm): Không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
Dữ liệu vào
2
3 2
1 2
2 3
4 4
1 2
1 3
2 4
3 4Kết quả ra
3
3 3 3
2 3 3
2 3 2
1 2 1
7
7 7 7 7 7 7 7
2 1 3 3 4 3 4
2 1 3 3 3 3 3
2 1 1 1 3 4 4
2 2 2 1 3 4 3
1 1 1 2 4 4 4
2 2 1 2 2 4 3
2 2 1 2 2 4 4Giải thích
Test này gồm hai kịch bản con (hai lần gọi create_map).
Kịch bản 1: create_map(3, 2, [1, 2], [2, 3]). Đây là ví dụ trong phần mô tả đề bài, hàm có thể trả về bản đồ kích thước \(K = 3\):
2 3 3
2 3 2
1 2 1
Kịch bản 2: create_map(4, 4, [1, 1, 2, 3], [2, 3, 4, 4]). Ở đây \(N = 4\), \(M = 4\) và các cặp quốc gia \((1,2)\), \((1,3)\), \((2,4)\), \((3,4)\) là kề nhau. Do đó, các cặp \((1,4)\) và \((2,3)\) không kề nhau.
Hàm có thể trả về bản đồ kích thước \(K = 7\) thoả mãn tất cả các điều kiện như trên. Bản đồ có thể nhỏ hơn; ví dụ, hàm có thể trả về bản đồ kích thước \(K = 2\):
3 1
4 2
Lưu ý rằng cả hai bản đồ đều thoả mãn \(K/N \leq 2\).
Chấm điểm
Đây là bài thi dạng hàm (signature-grader). Trình chấm mẫu đọc dữ liệu theo định dạng sau:
Dòng đầu tiên chứa một số nguyên \(T\) - số lượng kịch bản. Tiếp theo là mô tả của \(T\) kịch bản, mỗi kịch bản theo định dạng:
N M
A[0] B[0]
:
A[M-1] B[M-1]
Định dạng đầu ra:
P
Q[0] Q[1] ... Q[P-1]
C[0][0] ... C[0][Q[0]-1]
:
C[P-1][0] ... C[P-1][Q[P-1]-1]
Trong đó, \(P\) là độ dài của mảng \(C\) trả về bởi create_map, và \(Q[i]\) (\(0 \leq i < P\)) là độ dài của \(C[i]\). Lưu ý rằng dòng thứ 3 trong định dạng đầu ra cố ý để trống.
Điểm subtask 6 phụ thuộc vào giá trị \(K\):
- Nếu bất kỳ bản đồ nào trả về bởi
create_mapkhông thoả mãn tất cả các điều kiện, điểm subtask sẽ là \(0\). - Ngược lại, gọi \(R\) là giá trị lớn nhất của \(K/N\) trên tất cả các lần gọi
create_map. Khi đó, điểm thành phần được tính theo bảng sau:
| Giới hạn | Điểm |
|---|---|
| \(6 < R\) | \(0\) |
| \(4 < R \leq 6\) | \(14\) |
| \(3 < R \leq 4\) | \(28\) |
| \(2.5 < R \leq 3\) | \(42\) |
| \(2 < R \leq 2.5\) | \(49\) |
| \(R \leq 2\) | \(56\) |