Submission #1253336

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

worldmap

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

// Subtask 5 solution: N <= 15, any K <= 240 works. We choose K = 4*N.
// Build multi-source BFS from seeds to color grid satisfying adjacency constraints.

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    // 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;
    }

    int K = 4 * N;
    vector<vector<int>> grid(K, vector<int>(K, 0));
    queue<pair<int,int>> q;

    // Place initial seeds for each country at (3*(i-1), 3*(i-1))
    for(int i = 1; i <= N; i++){
        int r = 3*(i-1);
        int c = 3*(i-1);
        grid[r][c] = i;
        q.emplace(r, c);
    }

    int dr[4] = {-1,1,0,0}, dc[4] = {0,0,-1,1};
    auto can_color = [&](int r, int c, int col){
        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 k = grid[nr][nc];
            if(k != 0 && !adj[col][k]) return false;
        }
        return true;
    };

    // Multi-source BFS
    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 && can_color(nr, nc, col)){
                grid[nr][nc] = col;
                q.emplace(nr, nc);
            }
        }
    }

    // Fill any remaining zeros with a valid color
    for(int r = 0; r < K; r++){
        for(int c = 0; c < K; c++){
            if(grid[r][c] == 0){
                for(int col = 1; col <= N; col++){
                    if(can_color(r, c, col)){
                        grid[r][c] = col;
                        break;
                    }
                }
            }
        }
    }

    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