Submission #1288756

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288756		ecen30	World Map (IOI25_worldmap)	C++20	0 / 100	1 ms	572 KiB

worldmap

//testing Ai code
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <numeric>

using namespace std;

class WorldMapCreator {
public:
    vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
        // Build adjacency list for the country graph
        vector<set<int>> adj(N + 1);
        for (int i = 0; i < M; ++i) {
            adj[A[i]].insert(B[i]);
            adj[B[i]].insert(A[i]);
        }

        // Compute degrees
        vector<int> degree(N + 1, 0);
        for (int i = 1; i <= N; ++i) {
            degree[i] = adj[i].size();
        }

        // Special case: subtask 1 (path graph)
        if (M == N - 1 && N > 1) {
            bool is_path = true;
            for (int i = 1; i <= N; ++i) {
                if (degree[i] > 2) {
                    is_path = false;
                    break;
                }
            }
            if (is_path) {
                return create_path_map(N, A, B);
            }
        }

        // Special case: subtask 3 (M=4)
        if (M == 4) {
            return create_small_map(N, adj);
        }

        // Special case: subtask 4 (star-like: country 1 connected to all)
        if (adj[1].size() == N - 1) {
            return create_star_map(N, adj);
        }

        // General case: try to achieve K <= 2*N (aim for R <= 2)
        int target_K = max(2, min(240, 2 * N));
        return create_compact_map(N, adj, target_K);
    }

private:
    // Create map for path graph (subtask 1 & 2 when applicable)
    vector<vector<int>> create_path_map(int N, vector<int>& A, vector<int>& B) {
        vector<vector<int>> grid(2, vector<int>(N, 0));
        // Place countries in order: 1,2,3,...,N
        for (int i = 0; i < N; ++i) {
            grid[0][i] = i + 1;
            grid[1][i] = i + 1;
        }
        return grid; // 2 x N grid
    }

    // Create small map for M=4
    vector<vector<int>> create_small_map(int N, vector<set<int>>& adj) {
        if (N <= 4) {
            // Try 2x2 if possible
            vector<vector<int>> grid = {
                {1, 2},
                {3, 4}
            };
            if (validate_map(grid, N, adj)) {
                return grid;
            }
        }

        // Fall back to general compact
        return create_compact_map(N, adj, 2 * N);
    }

    // Create star map (country 1 connected to all)
    vector<vector<int>> create_star_map(int N, vector<set<int>>& adj) {
        int K = (int)ceil(sqrt(N));
        vector<vector<int>> grid(K, vector<int>(K, 1)); // Fill with country 1

        int idx = 0;
        for (int i = 2; i <= N; ++i) {
            int r = idx / K;
            int c = idx % K;
            if (r < K) {
                grid[r][c] = i;
            }
            ++idx;
        }

        // Ensure all neighbors of 1 touch it
        // Already satisfied since 1 is everywhere else

        return grid;
    }

    // General compact map: place countries in 2 rows, snake pattern
    vector<vector<int>> create_compact_map(int N, vector<set<int>>& adj, int max_K) {
        int K = min(max_K, 240);
        int rows = 2;
        int cols = (N + 1) / 2;
        if (cols > K) {
            cols = K;
            rows = (N + K - 1) / K;
        }
        if (rows * cols < N) {
            rows = (N + K - 1) / K;
        }

        vector<vector<int>> grid(rows, vector<int>(K, 0));
        vector<pair<int, int>> positions(N + 1, {-1, -1});
        int country = 1;

        // Place countries in snake order
        for (int r = 0; r < rows && country <= N; ++r) {
            int start_c = (r % 2 == 0) ? 0 : K - 1;
            int end_c = (r % 2 == 0) ? K : -1;
            int step = (r % 2 == 0) ? 1 : -1;

            for (int c = start_c; (step > 0 ? c < end_c : c > end_c) && country <= N; c += step) {
                grid[r][c] = country;
                positions[country] = {r, c};
                ++country;
            }
        }

        // Fill remaining cells with country 1 (or any high-degree country)
        int filler = 1;
        for (int i = 1; i <= N; ++i) {
            if (adj[i].size() > adj[filler].size()) {
                filler = i;
            }
        }
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < K; ++c) {
                if (grid[r][c] == 0) {
                    grid[r][c] = filler;
                }
            }
        }

        // If validation fails, expand
        if (!validate_map(grid, N, adj)) {
            return create_expanded_map(N, adj);
        }

        return grid;
    }

    // Fallback: larger map with clear borders
    vector<vector<int>> create_expanded_map(int N, vector<set<int>>& adj) {
        int side = (int)ceil(sqrt(N));
        int K = max(side + 2, min(240, N + 10)); // Extra border
        vector<vector<int>> grid(K, vector<int>(K, 0));

        // Place countries in grid
        int idx = 0;
        for (int i = 1; i <= N; ++i) {
            int r = 1 + (idx / side);
            int c = 1 + (idx % side);
            grid[r][c] = i;
            ++idx;
        }

        // Flood fill borders with high-degree country
        int border_country = 1;
        for (int i = 1; i <= N; ++i) {
            if (adj[i].size() > adj[border_country].size()) {
                border_country = i;
            }
        }

        for (int r = 0; r < K; ++r) {
            for (int c = 0; c < K; ++c) {
                if (grid[r][c] == 0) {
                    grid[r][c] = border_country;
                }
            }
        }

        return grid;
    }

    // Validate the map
    bool validate_map(const vector<vector<int>>& grid, int N, const vector<set<int>>& adj) {
        int K = grid.size();
        if (K == 0) return false;

        // Check all countries used
        vector<bool> used(N + 1, false);
        for (const auto& row : grid) {
            for (int c : row) {
                if (c < 1 || c > N) return false;
                used[c] = true;
            }
        }
        for (int i = 1; i <= N; ++i) {
            if (!used[i]) return false;
        }

        // Check required adjacencies
        vector<vector<bool>> observed_adj(N + 1, vector<bool>(N + 1, false));
        int dr[] = {-1, 0, 1, 0};
        int dc[] = {0, 1, 0, -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];
                    int nc = c + dc[d];
                    if (nr >= 0 && nr < K && nc >= 0 && nc < K) {
                        int v = grid[nr][nc];
                        if (u != v) {
                            observed_adj[u][v] = true;
                            observed_adj[v][u] = true;
                        }
                    }
                }
            }
        }

        // All required edges must be observed
        for (int u = 1; u <= N; ++u) {
            for (int v : adj[u]) {
                if (!observed_adj[u][v]) {
                    return false;
                }
            }
        }

        // No forbidden adjacencies
        for (int u = 1; u <= N; ++u) {
            for (int v = u + 1; v <= N; ++v) {
                if (adj[u].count(v) == 0 && observed_adj[u][v]) {
                    return false;
                }
            }
        }

        return true;
    }
};

// Global function required by judge
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    WorldMapCreator solver;
    return solver.create_map(N, M, A, B);
}

• 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