Submission #1263293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263293		fv3	World Map (IOI25_worldmap)	C++20	100 / 100	43 ms	2888 KiB

worldmap

#include "worldmap.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> DFS_long_order(vector<vector<int>>& adj) {
    const int n = adj.size();
    mt19937 mt(time(0));

    vector<int> order;

    vector<int> par(n, -1), vis(n);
    auto Dfs = [&](auto&& self, int node) -> void {
        order.push_back(node);
        vis[node] = 1;

        for (int child : adj[node]) if (!vis[child] && child != par[node]) {
            par[child] = node;
            self(self, child);
            return;
        }

        if (par[node] != -1) {
            self(self, par[node]);
        }
    };

    for (int i = 0; i < n; i++) {
        shuffle(adj[i].begin(), adj[i].end(), mt);
    }
    Dfs(Dfs, mt() % n);

    return order;
}

struct Up {
    int i, j;
    bool operator<(const Up& other) const {
        return make_pair(j - i, j) < make_pair(other.j - other.i, other.j);
    }
};

std::string to_string(Up up) {
    return "{" + to_string(up.i) + ", " + to_string(up.j) + "}";
}

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    const int K = 2 * N;

    vector<vector<int>> adj(N);
    for (int i = 0; i < M; i++) {
        A[i]--; B[i]--;
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }

    vector<int> order = DFS_long_order(adj);
    while (int(order.size()) < 2 * K) {
        order.push_back(order.back());
    }

    vector<set<int>> rem_neighbours(N);
    for (int i = 0; i < N; i++) {
        for (int node : adj[i]) {
            rem_neighbours[i].insert(node);
        }
    }
    for (int i = 0; i < int(order.size()) - 1; i++) {
        if (rem_neighbours[order[i]].count(order[i + 1])) {
            rem_neighbours[order[i]].erase(order[i + 1]);
        }
        if (rem_neighbours[order[i + 1]].count(order[i])) {
            rem_neighbours[order[i + 1]].erase(order[i]);
        }
    }

    vector<vector<int>> ans(K, vector<int>(K));
    auto Set = [&](int i, int j, int c) -> void {
        if (i >= 0 && i < K && j >= 0 && j < K && !ans[i][j]) ans[i][j] = c + 1;
    };

    set<Up> border;
    vector<int> vis(N);

    auto Place = [&](int i, int j, int oc, int c) -> void {
        ans[i][j] = c + 1;
        border.erase({i, j});

        Set(i - 1, j, oc);
        Set(i, j + 1, oc);

        if (i - 2 >= 0 && !ans[i - 2][j]) {
            border.insert({i - 2, j});
        }
        if (i - 1 >= 0 && j + 1 < K && !ans[i - 1][j + 1]) {
            border.insert({i - 1, j + 1});
        }
        if (j + 2 < K && !ans[i][j + 2]) {
            border.insert({i, j + 2});
        }
    };

    border.insert({K - 1, 0});
    for (int c = 0; !border.empty(); c++) {
        set<Up> newBorder;

        for (auto [i, j] : border) {
            Set(i, j, order[c]);
            if (i - 1 >= 0 && !ans[i - 1][j]) {
                newBorder.insert({i - 1, j});
            }
            if (j + 1 < K && !ans[i][j + 1]) {
                newBorder.insert({i, j + 1});
            }
        }
        swap(border, newBorder);

        if (vis[order[c]]) continue;

        vis[order[c]] = 1;
        for (int col : rem_neighbours[order[c]]) if (!vis[col]) {
            auto [i, j] = *border.begin();
            Place(i, j, order[c], col);
        }
    }

    return ans;
}

• 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