| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1250024 | testacc11 | World Map (IOI25_worldmap) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
// Build any valid K×K coloring (K ≤ 240) satisfying
// 1) each of 1..N appears at least once,
// 2) for every edge (u,v), at least one adjacent u–v in grid,
// 3) no adjacent-different pair beyond the given edges.
//
// This simple “column-strip” construction uses K = min(240, 2*M+2):
// – reserve columns 0..M–1 for each edge: we place [u;v] vertically at (0,i),(1,i)
// – fill the rest of the grid with the same color u of that column, so
// only u–v adjacencies occur, and any other adjacency is u–u.
// – ensure every isolated country gets a single cell in column K–1.
vector<vector<int>> create_map(int N, int M,
const vector<int>& A,
const vector<int>& B) {
int K = min(240, 2 * M + 2);
if (K < 2) K = 2;
vector<vector<int>> C(K, vector<int>(K, 1));
// Step 1: carve out each edge
for (int i = 0; i < M && i < K; ++i) {
int u = A[i], v = B[i];
// two‐cell vertical domino at rows 0&1, column i
C[0][i] = u;
C[1][i] = v;
// fill the rest of that column with u
for (int r = 2; r < K; ++r) C[r][i] = u;
}
// Step 2: place any country with no edges
vector<bool> seen(N+1,false);
for(int i=0;i<M;i++){
seen[A[i]]=seen[B[i]]=true;
}
int c = 0;
for(int j=1;j<=N;j++){
if(!seen[j]){
// put one isolated j in column M (or last if full)
int col = (c < K ? c : K-1);
C[K-1][col] = j;
++c;
}
}
return C;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
if(!(cin>>T))return 0;
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";
for(auto &row:C){
for(int i=0;i<K;i++){
cout<<(i?" ":"")<<row[i];
}
cout<<"\n";
}
}
return 0;
}