Submission #1262716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262716		fv3	세계 지도 (IOI25_worldmap)	C++20	93 / 100	43 ms	4168 KiB

worldmap

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

using namespace std;

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 = 5 * n / 2;

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

    }

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

    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: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 14 / 14
• Subtask 6: 49 / 56