Submission #1253391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253391		dreamnguyen	World Map (IOI25_worldmap)	C++20	0 / 100	15 ms	2116 KiB

worldmap

#include <vector>
#include <stack>
#include <algorithm>
#include <map>
#include <set>

std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
    int K = 2 * M + 1;

    std::map<int, std::multiset<int>> graph;

    for (int i = 0; i < M; ++i) {
        graph[A[i]].insert(B[i]);
        graph[B[i]].insert(A[i]);
    }
    int start = 1;
    for (int i = 1; i <= N; ++i) {
        if (graph[i].size() % 2 == 1) {
            start = i;
            break;
        }
    }

    std::vector<int> euler_path;
    std::stack<int> s;
    s.push(start);

    while (!s.empty()) {
        int u = s.top();
        if (graph[u].empty()) {
            euler_path.push_back(u);
            s.pop();
        } else {
            int v = *graph[u].begin();
            graph[u].erase(graph[u].find(v));
            graph[v].erase(graph[v].find(u));
            s.push(v);
        }
    }
    std::vector<std::vector<int>> map(K, std::vector<int>(K, 0));
    int x = 0, y = 0;
    int dx = 0, dy = 1;

    for (int i = 0; i + 1 < (int)euler_path.size(); ++i) {
        int a = euler_path[i];
        int b = euler_path[i + 1];

        map[x][y] = a;
        map[x + dx][y + dy] = b;

        x += dx;
        y += dy;

        if (y + 1 >= K) {
            x += 2;
            y = 0;
        }
    }

    // Lấp ô chưa dùng bằng quốc gia 1
    for (int i = 0; i < K; ++i)
        for (int j = 0; j < K; ++j)
            if (map[i][j] == 0)
                map[i][j] = 1;

    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