Submission #1289151

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289151		ecen30	세계 지도 (IOI25_worldmap)	C++20	15 / 100	15 ms	3436 KiB

worldmap

//testing AI Code
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>

using namespace std;

std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
    // 1. Precompute Adjacency Matrix
    // Adj[i][j] is true if country i is adjacent to country j.
    // Use 1-based indexing for countries (1 to N).
    std::vector<std::vector<bool>> Adj(N + 1, std::vector<bool>(N + 1, false));
    for (int k = 0; k < M; ++k) {
        Adj[A[k]][B[k]] = true;
        Adj[B[k]][A[k]] = true;
    }

    // Determine the isolation/hub color. Country 1 is a good general choice.
    // If the problem guarantees a map exists, we can use a structural construction.
    // The construction must guarantee K/N <= 2 (K=2N).
    int K = 2 * N;
    std::vector<std::vector<int>> C(K, std::vector<int>(K));

    // Iterate over the N x N blocks of size 2x2.
    for (int i = 0; i < N; ++i) { // Block row index (0 to N-1)
        for (int j = 0; j < N; ++j) { // Block column index (0 to N-1)
            int A_country = i + 1;
            int B_country = j + 1;

            // Coordinates of the top-left cell of the 2x2 block
            int r_start = 2 * i;
            int c_start = 2 * j;
            
            if (A_country == B_country) {
                // Case 1: Main Block (i=j). Fill with a single color i+1.
                C[r_start][c_start] = A_country;
                C[r_start][c_start + 1] = A_country;
                C[r_start + 1][c_start] = A_country;
                C[r_start + 1][c_start + 1] = A_country;
            } else if (Adj[A_country][B_country]) {
                // Case 2: Required Adjacency. Create an A-B boundary within the block.
                // This satisfies Condition 2: (A, B) must touch.
                // We ensure no other colors are involved in this block.
                C[r_start][c_start] = A_country;
                C[r_start][c_start + 1] = B_country;
                C[r_start + 1][c_start] = B_country;
                C[r_start + 1][c_start + 1] = A_country;
            } else {
                // Case 3: Forbidden Adjacency (A, B not adjacent).
                // Fill with an isolation color (Country 1) to satisfy Condition 3.
                // This assumes Country 1 is a "hub" or "universal connector" adjacent to all other countries.
                // Subtask 4 suggests this is a common case.
                int X_country = 1;
                
                // We must confirm that using X creates only allowed adjacencies.
                // The new adjacencies will be A-X and B-X (at the block boundaries).
                // Since A is adjacent to i-1, i+1, and B is adjacent to j-1, j+1,
                // we only need to check A-X and B-X.
                
                // The problem guarantees a solution exists, so this hub-filling strategy 
                // is likely intended for the optimal K/N solution.

                C[r_start][c_start] = X_country;
                C[r_start][c_start + 1] = X_country;
                C[r_start + 1][c_start] = X_country;
                C[r_start + 1][c_start + 1] = X_country;
            }
        }
    }

    // The construction satisfies:
    // 1. Presence: All N countries are on the diagonal blocks.
    // 2. Required Adjacency: Handled in Case 2.
    // 3. Forbidden Adjacency: 
    //    - Within Main/Forbidden blocks: No forbidden adjacencies are created.
    //    - Across block boundaries (i.e., A_country vs X_country): Requires X to be adjacent to A/B,
    //      which is satisfied if X=1 is the hub color (as in Subtask 4).
    
    return C;
}

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