제출 #1253351

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1253351		vuviet	세계 지도 (IOI25_worldmap)	C++20	15 / 100	58 ms	6980 KiB

worldmap

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

typedef vector<int> vi;

vector<vi> create_map(int n, int m, vi a, vi b) {
    vector<vi> adj(n + 1);
    for (int i = 0; i < m; i++) {
        adj[a[i]].push_back(b[i]);
        adj[b[i]].push_back(a[i]);
    }

    // Duyệt DFS xây cây
    vector<int> parent(n + 1, 0);
    vector<vi> child(n + 1);
    function<void(int)> dfs = [&](int u) {
        for (int v : adj[u]) {
            if (v == parent[u]) continue;
            if (parent[v]) continue;
            parent[v] = u;
            child[u].push_back(v);
            dfs(v);
        }
    };
    parent[1] = -1;
    dfs(1);

    // Euler tour
    vi ord;
    function<void(int)> dfs_euler = [&](int u) {
        ord.push_back(u);
        for (int v : child[u]) {
            dfs_euler(v);
            ord.push_back(u);
        }
    };
    dfs_euler(1); // kích thước = 2n - 1

    // Tạo hàng
    vector<vi> rows;
    for (int u : ord) rows.push_back({u});
    while ((int)rows.size() < 4 * n - 1)
        rows.push_back(rows.back());

    // Gán màu theo đường chéo
    int K = 4 * n;
    vector<vi> grid(K, vi(K, 0));
    for (int i = 0; i < 4 * n - 1; i++) {
        int len = min(i + 1, 4 * n - 1 - i);
        while ((int)rows[i].size() < len)
            rows[i].push_back(rows[i].back());
        int p = 0;
        for (int x = 0; x < K; x++) {
            int y = i - x;
            if (0 <= y && y < K && p < (int)rows[i].size())
                grid[x][y] = rows[i][p++];
        }
    }

    // ✅ Bổ sung dòng / cột cuối nếu còn ô chưa tô
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {
            if (grid[i][j] == 0)
                grid[i][j] = 1; // tô tạm bằng màu 1 (đã đảm bảo hợp lệ trước đó)
        }
    }

    return grid;
}

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