Submission #1253334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253334		vuviet	World Map (IOI25_worldmap)	C++20	5 / 100	8 ms	1096 KiB

worldmap

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

/**
 * N ≤ 15, M ≤ N*(N−1)/2
 * Chạy tối đa 50 lần → O(N^2·K^2) mỗi lần là hoàn toàn ổn với K ~ 4N ≤ 60.
 */

vector<vector<int>> create_map(int N, int M,
                              vector<int> A, vector<int> B) {
    // 1) Build adjacency matrix
    vector<vector<bool>> adj(N+1, vector<bool>(N+1, false));
    for(int i = 1; i <= N; i++) adj[i][i] = true;
    for(int i = 0; i < M; i++){
        adj[A[i]][B[i]] = adj[B[i]][A[i]] = true;
    }

    // 2) Chọn K đủ lớn: ta dùng K = 4*N
    int K = 4 * N;
    vector<vector<int>> grid(K, vector<int>(K, 0));

    // 3) Đặt seed ban đầu cho mỗi quốc gia tại (3*i, 3*i)
    queue<pair<int,int>> q;
    for(int i = 1; i <= N; i++){
        int r = 3*(i-1), c = 3*(i-1);
        grid[r][c] = i;
        q.emplace(r, c);
    }

    // 4) Multi‐source BFS
    int dr[4] = {-1,1,0,0}, dc[4] = {0,0,-1,1};
    auto can_color = [&](int cr, int cc, int color){
        // Đảm bảo với mỗi ô đã tô cạnh (cr,cc), nếu màu là k ≠ color
        // thì phải adj[color][k] == true
        for(int d = 0; d < 4; d++){
            int nr = cr + dr[d], nc = cc + dc[d];
            if(nr<0||nr>=K||nc<0||nc>=K) continue;
            int k = grid[nr][nc];
            if(k != 0 && !adj[color][k]) 
                return false;
        }
        return true;
    };

    while(!q.empty()){
        auto [r,c] = q.front(); q.pop();
        int col = 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;
            if(grid[nr][nc] != 0) continue;
            if(can_color(nr,nc,col)){
                grid[nr][nc] = col;
                q.emplace(nr,nc);
            }
        }
    }

    // 5) Nếu vẫn có ô bỏ trống (cực hiếm, chỉ xảy ra khi bị chặn giữa ba frontier),
    //    chúng ta điền tuỳ ý bằng một màu sao cho không vi phạm: thử các màu 1..N
    for(int r = 0; r < K; r++){
        for(int c = 0; c < K; c++){
            if(grid[r][c] == 0){
                for(int cand = 1; cand <= N; cand++){
                    if(can_color(r,c,cand)){
                        grid[r][c] = cand;
                        break;
                    }
                }
                // (về lý thuyết với đồ thị planar và seed đủ phân tán, vòng này hiếm khi chạy)
            }
        }
    }

    return grid;
}

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