Submission #1262874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262874		fv3	World Map (IOI25_worldmap)	C++20	15 / 100	19 ms	2372 KiB

worldmap

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

using namespace std;

#ifdef LOCAL
#include "/home/fv3/Desktop/prog/debug/debug.h"
#else
#define debug(...) 42
#endif

int n, m;
mt19937 mt(time(0));

optional<vector<vector<int>>> solve(vector<vector<int>>& adj) {
    vector<int> col;

    vector<int> vis(n), last(n, -1);
    vector<vector<int>> pos(n);

    int rem = n;
    auto Dfs = [&](auto&& self, int i) -> void {
        pos[i].push_back(col.size());
        col.push_back(i);

        if (!vis[i]) {
            vis[i] = 1;
            if (!--rem) return;
        }

        for (auto node : adj[i]) if (node != last[i] && !vis[node]) {
            last[node] = i;
            self(self, node);
            return;
        }

        if (last[i] >= 0) {
            self(self, last[i]);
        }
    };
    for (auto &list : adj) {
        shuffle(list.begin(), list.end(), mt);
    }
    Dfs(Dfs, mt() % n);

    assert(!rem);

    set<int> extra;
    for (int i = 0; i < n; i++) {
        extra.insert(pos[i][mt() % pos[i].size()]);
    }

    int lines = col.size() + 2*n;
    int K = 2 * n;

    vector<vector<pair<int, int>>> diags(2 * K - 1);
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < K; j++) {
            diags[K-1 + i - j].push_back({i, j});
        }
    }

    vector<set<int>> radj(n);
    for (int i = 0; i < n; i++) {
        for (auto node : adj[i]) {
            radj[i].insert(node);
        }
    }

    for (int i = 0; i < int(col.size()) - 1; i++) {
        if (radj[col[i]].count(col[i+1])) {
            radj[col[i]].erase(col[i+1]);
        }
        if (radj[col[i+1]].count(col[i])) {
            radj[col[i+1]].erase(col[i]);
        }
    }

    int diag = (2*K - 1 - lines) / 2;

    int sz = int(col.size());

    vector<int> extra_index(n);
    vector<vector<int>> ans(K, vector<int>(K, col[0] + 1));

    for (int i = 0; i < sz; i++) {
        for (auto [y, x] : diags[diag]) {
            ans[y][x] = col[i] + 1;
        }

        diag++;
        if (!extra.count(i)) continue;
        extra_index[col[i]] = diag;

        for (int _ = 0; _ < 2; _++) {
            for (auto [y, x] : diags[diag]) {
                ans[y][x] = col[i] + 1;
            }
            diag++;
        }
    }

    while (diag < 2 * K - 1) {
        for (auto [y, x] : diags[diag++]) {
            ans[y][x] = col.back() + 1;
        }
    }

    rem = n;
    queue<int> que;

    for (int c = 0; c < n; c++) {
        if (diags[extra_index[c]].size() < radj[c].size()) continue;
        que.push(c);
        vis[c] = 1;
        rem--;
    }

    while (!que.empty()) {
        int s = que.front();
        que.pop();

        int i = 0;
        for (auto c : radj[s]) {
            auto [y, x] = diags[extra_index[s]][i];
            ans[y][x] = c + 1;
            i++;
        }

        for (int c = 0; c < n; c++) {
            if (vis[c] || !radj[c].count(s)) continue;
            radj[c].erase(s);

            if (diags[extra_index[c]].size() < radj[c].size()) continue;
            que.push(c);
            vis[c] = 1;
            rem--;
        }

        for (int c = 0; c < n; c++) {
            if (vis[c] || diags[extra_index[c]].size() < radj[c].size()) continue;
            que.push(c);
            vis[c] = 1;
            rem--;
        }

    }

    debug(col);
    if (rem) {
        exit(0);
        return {};
    }
    return ans;
}

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    n = N; m = M;

    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]);
    }

    for (int i = 0; i < n; i++) {
        if (int(adj[i].size()) == N - 1) {
            const int K = 2 * N;
            vector<vector<int>> ans(K, vector<int>(K, i + 1));

            int x = 0, y = 0;
            for (int j = 0; j < M; j++) {
                ans[y+1][x+1] = A[j] + 1;
                ans[y+1][x+2] = B[j] + 1;

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

            return ans;
        }
    }

    auto ans = solve(adj);
    while (!ans) ans = solve(adj);
    return *ans;
}

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