Submission #1253389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253389		dreamnguyen	World Map (IOI25_worldmap)	C++20	0 / 100	1 ms	580 KiB

worldmap

#include <vector>
#include <set>
#include <algorithm>
#include "worldmap.h"
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
    int K = N * 7; // Đảm bảo R = K / N > 6 ⇒ "phá" subtask 6

    std::vector<std::vector<int>> grid(K, std::vector<int>(K, 0));

    // Tập hợp các cặp liền kề hợp lệ
    std::set<std::pair<int, int>> neighbor_set;
    for (int i = 0; i < M; ++i) {
        neighbor_set.insert({A[i], B[i]});
        neighbor_set.insert({B[i], A[i]});
    }

    // Tô từng cặp liền kề vào các vùng không giao nhau
    int row = 0;
    for (int i = 0; i < M; ++i) {
        int a = A[i], b = B[i];
        // Vị trí riêng biệt, đảm bảo không chạm các ô khác
        int col = 0;

        grid[row][col] = a;
        grid[row][col + 1] = b;
        row += 3; // cách dòng để không chạm nhau
    }

    // Tô mỗi quốc gia còn thiếu ít nhất 1 lần
    std::vector<bool> seen(N + 1, false);
    for (int i = 0; i < K; ++i)
        for (int j = 0; j < K; ++j)
            if (grid[i][j] != 0)
                seen[grid[i][j]] = true;

    row = K - 1;
    for (int c = 1; c <= N; ++c) {
        if (!seen[c]) {
            grid[row][c] = c;
        }
    }

    // Tô toàn bộ ô còn lại bằng quốc gia 1
    for (int i = 0; i < K; ++i)
        for (int j = 0; j < K; ++j)
            if (grid[i][j] == 0)
                grid[i][j] = 1;

    // Đảm bảo: mỗi ô liền kề có màu khác đều là cặp hợp lệ
    for (int i = 0; i < K; ++i) {
        for (int j = 0; j < K; ++j) {
            if (i + 1 < K && grid[i][j] != grid[i + 1][j]) {
                if (!neighbor_set.count({grid[i][j], grid[i + 1][j]})) {
                    // Nếu là cặp không hợp lệ ⇒ sửa lại thành cùng màu
                    grid[i + 1][j] = grid[i][j];
                }
            }
            if (j + 1 < K && grid[i][j] != grid[i][j + 1]) {
                if (!neighbor_set.count({grid[i][j], grid[i][j + 1]})) {
                    grid[i][j + 1] = grid[i][j];
                }
            }
        }
    }

    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