Submission #1249923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249923		cpsbd66	World Map (IOI25_worldmap)	C++20	Compilation error	0 ms	0 KiB

worldmap

#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;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccUWfDy9.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccb8Z2tb.o:worldmap.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccUWfDy9.o: in function `main':
grader.cpp:(.text.startup+0x635): undefined reference to `create_map(int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status