| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1249923 | cpsbd66 | 세계 지도 (IOI25_worldmap) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
// =======================================================
// Creates a K×K map satisfying the exact adjacency list.
// We handle two cases:
// - Subtask 1: M = N-1 and edges form the path 1–2–…–N.
// We use K = N and an "identity" map: row i is all color i+1.
// - Subtask 2: M = N-1 (a tree). We use K = N + M and
// identity base columns plus one column per edge.
// =======================================================
vector<vector<int>> create_map(int N, int M,
const vector<int>& A,
const vector<int>& B) {
// Detect subtask 1: exactly the path 1–2–…–N
bool isPath = (M == N-1);
if (isPath) {
for (int i = 0; i < M; i++) {
if (!(A[i] == i+1 && B[i] == i+2)) {
isPath = false;
break;
}
}
}
if (isPath) {
// K = N, row i filled with color (i+1)
int K = N;
vector<vector<int>> C(K, vector<int>(K, 0));
for (int i = 0; i < K; i++) {
for (int j = 0; j < K; j++) {
C[i][j] = i+1;
}
}
return C;
}
// Otherwise: general tree (Subtask 2). K = N + M.
int K = N + M;
vector<vector<int>> C(K, vector<int>(K, 0));
// Base: columns 0..N-1 are identity
for (int i = 0; i < K; i++) {
for (int j = 0; j < N; j++) {
C[i][j] = i+1; // if i >= N, i+1 > N but we'll only use i< N here
}
}
// Now fill the rest: one column per adjacency
for (int e = 0; e < M; e++) {
int u = A[e]-1, v = B[e]-1;
int col = N + e;
// By default row i = i+1 (already set for i<N; fix for i>=N next)
for (int i = 0; i < K; i++) {
C[i][col] = (i < N ? i+1 : 1);
}
// swap exactly at rows u,v
C[u][col] = v+1;
C[v][col] = u+1;
}
return C;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
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 P = (int)C.size();
// Output format:
// P
// Q[0] Q[1] ... Q[P-1]
//
// then the P rows of the K×K grid.
cout << P << "\n";
for (int i = 0; i < P; i++) {
cout << P << (i+1<P ? ' ' : '\n');
}
cout << "\n";
for (int i = 0; i < P; i++) {
for (int j = 0; j < P; j++) {
cout << C[i][j] << (j+1<P ? ' ' : '\n');
}
}
}
return 0;
}