Submission #1252515

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

worldmap

#include "worldmap.h"
#include <vector>
#include <queue>

using namespace std;

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    const int K = 2 * N;
    vector<vector<int>> ans(K, vector<int>(K, 0));
    vector<vector<int>> adj(N);
    vector<vector<bool>> used(K, vector<bool>(K, false));
    vector<pair<int, int>> pos(N, {-1, -1});
    for (int i = 0; i < M; ++i) {
        int u = A[i] - 1;
        int v = B[i] - 1;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    queue<int> q;
    q.push(0);
    pos[0] = {K / 2, K / 2};
    ans[K / 2][K / 2] = 1;
    used[K / 2][K / 2] = true;
    const int dx[4] = {-1, 1, 0, 0};
    const int dy[4] = {0, 0, -1, 1};
    while (!q.empty()) {
        int u = q.front(); q.pop();
        auto [x, y] = pos[u];
        for (int v : adj[u]) {
            if (pos[v].first != -1) continue;
            for (int d = 0; d < 4; ++d) {
                int nx = x + dx[d], ny = y + dy[d];
                if (nx < 0 || ny < 0 || nx >= K || ny >= K) continue;
                if (used[nx][ny]) continue;

                pos[v] = {nx, ny};
                ans[nx][ny] = v + 1;
                used[nx][ny] = true;
                q.push(v);
                break;
            }
        }
    }
    for (int i = 0; i < N; ++i) {
        if (pos[i].first != -1) continue;
        for (int x = 0; x < K; ++x) {
            for (int y = 0; y < K; ++y) {
                if (!used[x][y]) {
                    ans[x][y] = i + 1;
                    used[x][y] = true;
                    pos[i] = {x, y};
                    goto next;
                }
            }
        }
        next:;
    }

    return ans;
}

• 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