Submission #1253375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253375		vuviet	World Map (IOI25_worldmap)	C++20	0 / 100	17 ms	2372 KiB

worldmap

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;

// Đơn giản chỉ dành cho N <= 15.
// Ý tưởng: với mỗi cặp liền kề (u,v), tạo hai dòng 1×2 để thể hiện biên giới u-v và v-u.
// Sau đó, đảm bảo mỗi màu j xuất hiện ít nhất một lần bằng các dòng đơn sắc.

vector<vector<int>> create_map(int N, int M, vi A, vi B) {
    // Số dòng cần: 2*M dòng cho các cặp, + N dòng cho mỗi quốc gia xuất hiện.
    int R = max(2 * M + N, 2);
    int K = R;
    // Tạo bản đồ K×K, khởi tạo toàn bộ là màu 1 (hoặc bất kỳ).
    vector<vector<int>> C(K, vector<int>(K, 1));

    // Thêm các biên giới cho mỗi cặp liền kề.
    for (int i = 0; i < M; ++i) {
        int u = A[i], v = B[i];
        int r1 = 2 * i;
        int r2 = 2 * i + 1;
        // Dòng thể hiện u cạnh v
        C[r1][0] = u;
        C[r1][1] = v;
        // Dòng thể hiện v cạnh u
        C[r2][0] = v;
        C[r2][1] = u;
    }

    // Đảm bảo mỗi màu j xuất hiện ít nhất 1 lần
    int base = 2 * M;
    for (int j = 1; j <= N; ++j) {
        int r = base + (j - 1);
        C[r][0] = j;
        C[r][1] = j;
    }

    return C;
}

• 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