제출 #1253342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1253342		vuviet	World Map (IOI25_worldmap)	C++20	0 / 100	5 ms	840 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<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;
    vector<vi> grid(K, vi(K, 0));
    queue<pair<int, int>> q;

    // Gieo hạt ban đầu
    for (int i = 1; i <= N; i++) {
        int r = 3 * (i - 1), 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 color) {
        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[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 && can_color(nr, nc, col)) {
                grid[nr][nc] = col;
                q.emplace(nr, nc);
            }
        }
    }

    // Điền ô trống còn lại nếu có
    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: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 7
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 56