Submission #1273677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273677		lucas110550	World Map (IOI25_worldmap)	C++20	58 / 100	145 ms	19920 KiB

worldmap

#include <bits/stdc++.h>
using namespace std;

/*  Construction Overview
 *
 *  The goal is to output a K×K grid (K ≤ 240) whose adjacency graph is exactly the
 *  given undirected graph G = (V, E) (|V| = N ≤ 40).  The following simple scheme
 *  works for any connected graph.
 *
 *  1.  Choose an arbitrary root (vertex 0).  Build a spanning tree T of G using BFS.
 *
 *  2.  Perform a DFS walk on T that starts at the root and returns to it:
 *
 *               walk = v0 , v1 , v2 , … , vL‑1           (L = 2·N‑1)
 *
 *       Consecutive vertices in the walk are always adjacent in G (they are tree edges).
 *
 *  3.  For every occurrence vi of a vertex we allocate three consecutive columns:
 *
 *               [ left‑buffer | central | right‑buffer ]
 *
 *       All three columns are initially filled with the colour vi+1.
 *
 *  4.  For each vertex v we take the *first* occurrence of v in the walk,
 *        look at its central column, and embed all incident edges of v vertically:
 *
 *               for the j‑th neighbour w of v (0‑based)
 *                         put colour (w+1) into row 2·j of that central column.
 *
 *        Row 2·j contains w, row 2·j+1 contains the default colour v.
 *        Hence the vertical pair (row 2·j , row 2·j+1) yields the required adjacency
 *        {v , w}.  Different neighbours are separated by at least one row of colour v,
 *        therefore no unwanted edge (w1 , w2) is created.
 *
 *  5.  The walk guarantees that, for every tree edge {vi , vi+1},
 *        the right‑buffer column of vi and the left‑buffer column of vi+1 are
 *        adjacent in every row, giving the horizontal adjacency {vi , vi+1}.
 *
 *  6.  The walk contains each vertex at least once, so every colour appears.
 *        Every edge of G appears either as a vertical adjacency in step 4
 *        (for all edges) or as a horizontal adjacency in step 5 (for tree edges,
 *        which are a subset of all edges).  No other pairs of different colours are
 *        adjacent, because:
 *              – inside a block all horizontal neighbours have the same colour,
 *              – the only horizontal neighbours of a column with a “different” colour w
 *                are the left/right buffers, both coloured with the block’s own vertex,
 *              – vertical neighbours are either the same colour or (v , w) where (v , w)
 *                is an original edge.
 *
 *  7.  Grid size:
 *              rows_needed = 2·Δ + 1  where Δ = max degree (Δ ≤ 39) ⇒ rows_needed ≤ 79.
 *              columns = 3·L = 3·(2·N‑1) ≤ 3·79 = 237.
 *              Let K = columns (the larger dimension).  K ≤ 237 ≤ 240.
 *              Rows beyond rows_needed are filled with a copy of the last real row,
 *              which creates only same‑colour vertical adjacencies, so the constraints
 *              still hold.
 *
 *  The construction satisfies all required conditions and works for any
 *  connected graph with the given limits.
 */

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
        // ----- build adjacency list -----
        vector<vector<int>> adj(N);
        for (int i = 0; i < M; ++i) {
                int u = A[i] - 1;
                int v = B[i] - 1;
                adj[u].push_back(v);
                adj[v].push_back(u);
        }

        // ----- compute maximal degree -----
        int maxDeg = 0;
        for (int v = 0; v < N; ++v) maxDeg = max(maxDeg, (int)adj[v].size());

        // ----- build a spanning tree (BFS) -----
        vector<vector<int>> treeAdj(N);
        vector<int> parent(N, -1);
        queue<int> q;
        q.push(0);
        parent[0] = 0;
        while (!q.empty()) {
                int v = q.front(); q.pop();
                for (int u : adj[v]) {
                        if (parent[u] == -1) {
                                parent[u] = v;
                                treeAdj[v].push_back(u);
                                treeAdj[u].push_back(v);
                                q.push(u);
                        }
                }
        }

        // ----- DFS walk on the tree (consecutive vertices are edges) -----
        vector<int> walk;
        function<void(int,int)> dfs = [&](int v, int p) {
                walk.push_back(v);
                for (int u : treeAdj[v]) {
                        if (u == p) continue;
                        dfs(u, v);
                        walk.push_back(v);
                }
        };
        dfs(0, -1);
        int L = (int)walk.size();                                // L = 2·N‑1
        int cols = 3 * L;                                                // total columns
        int rowsNeeded = 2 * maxDeg + 1;                   // vertical space for neighbour cells
        int K = cols;                                                    // K ≤ 237 ≤ 240

        // ----- initialise the grid (filled later) -----
        vector<vector<int>> grid(K, vector<int>(K, 1));   // any colour, will be overwritten

        // ----- locate the first occurrence of each vertex in the walk -----
        vector<int> firstOcc(N, -1);
        for (int i = 0; i < L; ++i) {
                int v = walk[i];
                if (firstOcc[v] == -1) firstOcc[v] = i;
        }

        // ----- fill the basic structure: three columns per occurrence -----
        for (int i = 0; i < L; ++i) {
                int v = walk[i];
                int base = i * 3;
                for (int r = 0; r < rowsNeeded; ++r) {
                        int col = v + 1;                                          // colours are 1‑based
                        grid[r][base]    = col;   // left buffer
                        grid[r][base + 1] = col;   // central column (temporary)
                        grid[r][base + 2] = col;   // right buffer
                }
        }

        // ----- place neighbours vertically inside the central column of the
        //              first occurrence of each vertex -----
        for (int v = 0; v < N; ++v) {
                int occ = firstOcc[v];
                if (occ == -1) continue;                                 // should not happen for a connected graph
                int centralCol = occ * 3 + 1;
                int idx = 0;
                for (int w : adj[v]) {
                        int row = 2 * idx;                                      // even rows are reserved for neighbours
                        grid[row][centralCol] = w + 1;          // place colour of neighbour
                        ++idx;
                }
        }

        // ----- fill the remaining rows (if any) with a copy of the last real row -----
        if (rowsNeeded < K) {
                for (int r = rowsNeeded; r < K; ++r) {
                        for (int c = 0; c < K; ++c) {
                                grid[r][c] = grid[rowsNeeded - 1][c];
                        }
                }
        }

        return grid;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 14 / 14
• Subtask 6: 14 / 56