| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1250018 | testacc11 | World Map (IOI25_worldmap) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
// --------------------------------------------------
// Problem: World Map
// Implementation of create_map for an arbitrary adjacency graph with 1 ≤ N ≤ 40, M edges.
// Guaranteed a valid map exists. Here we implement a simple constructive strategy.
// --------------------------------------------------
vector<vector<int>> create_map(int N, int M,
const vector<int>& A,
const vector<int>& B) {
// Simple construction:
// Use grid of size K = 2 * M (at most 2*N*(N-1)/2 = N*(N-1) ≤ 1560, capped to 240)
int K = min(240, 2 * M + 1);
if (K < 2) K = 2;
vector<vector<int>> C(K, vector<int>(K, 1));
// Place each required adjacency as a vertical pair in its own column
for (int i = 0; i < M && i < K; ++i) {
C[0][i] = A[i];
C[1][i] = B[i];
}
// Ensure every country appears at least once
for (int j = 1; j <= N; ++j) {
bool used = false;
for (int i = 0; i < M && i < K; ++i) {
if (A[i] == j || B[i] == j) { used = true; break; }
}
if (!used) {
// place at bottom-right
C[K-1][K-1] = j;
}
}
return C;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin >> T;
while (T--) {
int N, M;
cin >> N >> M;
vector<int> A(M), B(M);
for (int i = 0; i < M; ++i) {
cin >> A[i] >> B[i];
}
auto C = create_map(N, M, A, B);
int K = C.size();
cout << K << "\n";
cout << K;
for (int i = 0; i < K; ++i) {
for (int j = 0; j < (int)C[i].size(); ++j) {
cout << (j == 0 ? '\n' : ' ') << C[i][j];
}
}
cout << '\n';
}
return 0;
}