Submission #1274816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274816		mehrzad	세계 지도 (IOI25_worldmap)	C++20	72 / 100	66 ms	9544 KiB

worldmap

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

/*  Implementation of create_map
    Constructs a square map (K x K) satisfying the given adjacency constraints.
    The construction works for any connected graph with N <= 40.
*/

vector<vector<int>> create_map(int N, int M,
                               vector<int> A, vector<int> B) {

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

    // Build a spanning tree (BFS)
    int root = 1;                     // any vertex works (graph is guaranteed to be connected)
    vector<int> parent(N + 1, -1);
    vector<int> depth(N + 1, 0);
    queue<int> q;
    parent[root] = 0;
    q.push(root);
    vector<int> bfs_order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        bfs_order.push_back(u);
        for (int v : adj[u]) if (parent[v] == -1) {
            parent[v] = u;
            depth[v] = depth[u] + 1;
            q.push(v);
        }
    }

    // Children lists of the tree
    vector<vector<int>> children(N + 1);
    for (int v = 1; v <= N; ++v) {
        if (parent[v] > 0) children[parent[v]].push_back(v);
    }

    // Determine which edges are tree edges; others become "holes"
    vector<vector<int>> holes(N + 1);
    for (int i = 0; i < M; ++i) {
        int u = A[i], v = B[i];
        if (parent[u] == v || parent[v] == u) continue;        // tree edge
        // choose the endpoint nearer to the root as the host for the hole
        int host, other;
        if (depth[u] < depth[v] ||
            (depth[u] == depth[v] && u < v)) {
            host = u; other = v;
        } else {
            host = v; other = u;
        }
        holes[host].push_back(other);
    }

    // Width needed to place all holes with a separating cell of the host color
    int maxHole = 0;
    for (int v = 1; v <= N; ++v) maxHole = max(maxHole, (int)holes[v].size());
    int W = 2 * maxHole + 1;
    if (W == 0) W = 1;                 // at least one column

    // Helper to create rows
    auto makeRow = [&](int col) -> vector<int> {
        return vector<int>(W, col);
    };
    auto makeMiddleRow = [&](int col) -> vector<int> {
        vector<int> row(W, col);
        for (int i = 0; i < (int)holes[col].size(); ++i) {
            int c = 2 * i + 1;                       // guaranteed < W
            row[c] = holes[col][i];
        }
        return row;
    };

    vector<vector<int>> rows;

    // Depth‑first construction of the map
    function<void(int)> dfs = [&](int v) {
        // top row of vertex v
        rows.push_back(makeRow(v));
        // middle row (contains holes)
        rows.push_back(makeMiddleRow(v));
        // a row of v that will sit before the first child (acts as a separator)
        rows.push_back(makeRow(v));

        for (int c : children[v]) {
            dfs(c);                     // child's whole block
            rows.push_back(makeRow(v)); // separator after this child
        }
    };
    dfs(root);

    int R = (int)rows.size();
    int K = max(R, W);                 // final square size

    // If we have fewer rows than K, pad with rows of the root color
    while ((int)rows.size() < K) rows.push_back(makeRow(root));

    // Pad each row to length K using its own primary color (the first element)
    for (auto &row : rows) {
        int primary = row[0];
        while ((int)row.size() < K) row.push_back(primary);
    }

    // At this point rows.size() == K and each row has K elements.
    return rows;
}

• 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: 28 / 56