제출 #1253343

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

worldmap

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

typedef vector<int> vi;

// Hàm tạo bản đồ thỏa mãn các điều kiện đề bài
vector<vi> create_map(int N, int M, vi A, vi B) {
    // Danh sách kề dạng ma trận
    vector<vector<bool>> adj(N + 1, vector<bool>(N + 1, false));
    for (int i = 0; i < M; i++) {
        adj[A[i]][B[i]] = adj[B[i]][A[i]] = true;
    }

    int K = 4 * N; // K vừa đủ với N <= 15
    vector<vi> grid(K, vi(K, 0));
    queue<pair<int, int>> q;

    // Bước 1: Gieo hạt ban đầu cho mỗi quốc gia
    for (int i = 1; i <= N; i++) {
        int r = 3 * (i - 1), c = 3 * (i - 1);
        grid[r][c] = i;
        q.emplace(r, c);
    }

    // Hàm kiểm tra có thể tô màu tại (r,c) không
    auto can_color = [&](int r, int c, int color) {
        int dr[] = {-1, 1, 0, 0};
        int dc[] = {0, 0, -1, 1};
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= K || nc < 0 || nc >= K) continue;
            int neighbor = grid[nr][nc];
            if (neighbor != 0 && !adj[color][neighbor]) return false;
        }
        return true;
    };

    // Bước 2: Multi-source BFS để lan màu
    while (!q.empty()) {
        auto [r, c] = q.front(); q.pop();
        int color = grid[r][c];
        int dr[] = {-1, 1, 0, 0};
        int dc[] = {0, 0, -1, 1};
        for (int d = 0; d < 4; d++) {
            int nr = r + dr[d], nc = c + dc[d];
            if (nr < 0 || nr >= K || nc < 0 || nc >= K) continue;
            if (grid[nr][nc] == 0 && can_color(nr, nc, color)) {
                grid[nr][nc] = color;
                q.emplace(nr, nc);
            }
        }
    }

    // Bước 3: Điền các ô còn trống (hiếm gặp)
    for (int r = 0; r < K; r++) {
        for (int c = 0; c < K; c++) {
            if (grid[r][c] == 0) {
                for (int color = 1; color <= N; color++) {
                    if (can_color(r, c, color)) {
                        grid[r][c] = color;
                        break;
                    }
                }
            }
        }
    }

    // ============================
    // KIỂM TRA ĐẦU RA (ASSERTIONS)
    // ============================

    // Điều kiện 1: Mỗi quốc gia phải xuất hiện ít nhất một lần
    vector<bool> used(N + 1, false);
    for (int r = 0; r < K; r++)
        for (int c = 0; c < K; c++) {
            int color = grid[r][c];
            assert(1 <= color && color <= N);
            used[color] = true;
        }
    for (int i = 1; i <= N; i++) assert(used[i]);

    // Điều kiện 2: Mỗi cặp (A[i], B[i]) phải có ít nhất một cặp ô liền kề
    set<pair<int, int>> required;
    for (int i = 0; i < M; i++) {
        required.insert({A[i], B[i]});
        required.insert({B[i], A[i]});
    }

    set<pair<int, int>> seen;
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};
    for (int r = 0; r < K; r++) {
        for (int c = 0; c < K; c++) {
            int u = grid[r][c];
            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d], nc = c + dc[d];
                if (nr < 0 || nr >= K || nc < 0 || nc >= K) continue;
                int v = grid[nr][nc];
                if (u != v) {
                    seen.insert({u, v});
                }
            }
        }
    }

    for (int i = 0; i < M; i++) {
        assert(seen.count({A[i], B[i]}) || seen.count({B[i], A[i]}));
    }

    // Điều kiện 3: Không được có cặp màu khác nhau cạnh nhau nếu không nằm trong danh sách
    for (int r = 0; r < K; r++) {
        for (int c = 0; c < K; c++) {
            int u = grid[r][c];
            for (int d = 0; d < 4; d++) {
                int nr = r + dr[d], nc = c + dc[d];
                if (nr < 0 || nr >= K || nc < 0 || nc >= K) continue;
                int v = grid[nr][nc];
                if (u != v) {
                    assert(adj[u][v]); // chỉ được phép kề nếu có liên kết
                }
            }
        }
    }

    return grid;
}

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