Submission #1252637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252637		dreamnguyen	World Map (IOI25_worldmap)	C++20	0 / 100	1 ms	328 KiB

worldmap

#include "worldmap.h"
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    // 1. Xây dựng đồ thị liền kề
    vector<vector<int>> adj(N+1);
    for (int i = 0; i < M; i++) {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }

    // 2. DFS để xác định parent và depth của mỗi node
    vector<int> parent(N+1, 0);
    vector<int> depth(N+1, 0);
    vector<bool> visited(N+1, false);
    
    function<void(int)> dfs = [&](int u) {
        visited[u] = true;
        for (int v : adj[u]) {
            if (!visited[v]) {
                parent[v] = u;
                depth[v] = depth[u] + 1;
                dfs(v);
            }
        }
    };
    
    dfs(1); // Bắt đầu DFS từ quốc gia 1

    // 3. Tạo bản đồ với K = N
    int K = N;
    vector<vector<int>> map(K, vector<int>(K, 1)); // Khởi tạo toàn bộ là 1

    // 4. Điền màu theo thứ tự DFS
    // - Mỗi hàng i đại diện cho quốc gia i+1
    // - Đảm bảo parent và child liền kề nhau
    for (int i = 0; i < K; i++) {
        int country = i + 1;
        map[i][0] = country; // Cột đầu tiên là quốc gia tương ứng
        
        // Đặt parent của quốc gia này liền kề
        if (parent[country] != 0) {
            int p = parent[country];
            map[i][1] = p; // Ô bên phải là parent
        }
    }

    return map;
}

• 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