Submission #1249532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249532		jerry	World Map (IOI25_worldmap)	C++20	100 / 100	21 ms	2888 KiB

worldmap

#include "worldmap.h"

#include <assert.h>

std::vector<int> adj[45];
std::vector<int> ord;
int ans[95][95];
bool seen[45];

void dfs(int at) {
    seen[at] = true;
    ord.push_back(at);
    for (int u : adj[at]) {
        if (!seen[u]) {
            dfs(u);
            ord.push_back(at);
        }
    }
}

std::vector<std::vector<int>> create_map(int n, int m, std::vector<int> a, std::vector<int> b) {
    for (int i = 0; i < n; i++)
        adj[i].clear();
    for (int i = 0; i < m; i++) {
        adj[a[i] - 1].push_back(b[i] - 1);
        adj[b[i] - 1].push_back(a[i] - 1);
    }

    ord.clear();
    for (int i = 0; i < n; i++)
        seen[i] = false;
    dfs(0);

    for (int i = 0; i < 2 * n; i++)
        for (int j = 0; j < 2 * n; j++)
            ans[i][j] = ord.back();

    for (int i = 0; i < n; i++)
        seen[i] = false;
    int diag = 0;
    for (int u : ord) {
        for (int i = 0; i < 4 * n; i++) {
            int r = i, c = diag - i;
            if (0 <= r && r < 2 * n && 0 <= c && c < 2 * n)
                ans[r][c] = u;
        }
        diag++;

        if (seen[u]) {
            continue;
        }
        seen[u] = true;

        std::vector<int> here;
        for (int v : adj[u])
            if (seen[v])
                here.push_back(v);

        for (int i = 0; i < 4 * n; i++) {
            int r = i, c = diag - i;
            if (0 <= r && r < 2 * n && 0 <= c && c < 2 * n) {
                if (here.empty())
                    ans[r][c] = u;
                else {
                    ans[r][c] = here.back();
                    here.pop_back();
                }
            }
        }
        diag++;
        assert(here.empty());

        for (int i = 0; i < 4 * n; i++) {
            int r = i, c = diag - i;
            if (0 <= r && r < 2 * n && 0 <= c && c < 2 * n)
                ans[r][c] = u;
        }
        diag++;
    }

    std::vector<std::vector<int>> result;
    for (int i = 0; i < 2 * n; i++) {
        for (int j = 0; j < 2 * n; j++)
            ans[i][j]++;
        result.emplace_back(ans[i], ans[i] + 2 * n);
    }
    return result;
}

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