제출 #1252952

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1252952		fasterthanyou	World Map (IOI25_worldmap)	C++20	29 / 100	13 ms	2116 KiB

worldmap

#include <bits/stdc++.h>

#include <ranges>
using namespace std;

#ifdef LOCAL
#include "../../debug.h"
#else
#define debug(...) 42
#endif

namespace utils {
template <typename T>
bool chMax(T& target, const T& value) {
    if (value > target) {
        target = value;
        return true;
    }
    return false;
}

template <typename T>
bool chMin(T& target, const T& value) {
    if (value < target) {
        target = value;
        return true;
    }
    return false;
}
}  // namespace utils
using namespace utils;

using ll = long long;
using ld = long double;
using mp = vector<vector<int>>;
const char el = '\n';

mp create_map(int N, int M, vector<int> A, vector<int> B) {
    set<pair<int, int>> adj;
    vector<vector<int>> G(N);
    for (int i = 0; i < M; ++i) {
        G[A[i] - 1].push_back(B[i] - 1);
        G[B[i] - 1].push_back(A[i] - 1);
        if (A[i] > B[i]) {
            swap(A[i], B[i]);
        }
        adj.insert({A[i] - 1, B[i] - 1});
    }

    vector<bool> vst(N, false);
    function<vector<vector<int>>(int, int)> dfs = [&](int u, int p) {
        vst[u] = true;

        vector<mp> intermediate_sols;
        int total_len = 0;
        for (int v : G[u]) {
            if (v == p) continue;
            if (!vst[v]) {
                mp sub = dfs(v, u);
                intermediate_sols.push_back(sub);
                total_len += sub.size();
                int tu = u, tv = v;
                if (tu > tv) {
                    swap(tu, tv);
                }
                adj.erase({tu, tv});
            } else {
                int tu = u, tv = v;
                if (tu > tv) {
                    swap(tu, tv);
                }
                if (adj.count({tu, tv}) > 0) {
                    adj.erase({tu, tv});
                    mp sub = {{v + 1}};
                    intermediate_sols.push_back(sub);
                    total_len += 1;
                }
            }
        }

        if (total_len == 0) {
            return mp{{u + 1}};
        }

        mp ret(total_len + 2, vector<int>(total_len + 2, -1));
        int k = 1;
        for (auto sub : intermediate_sols) {
            int sub_len = sub.size();
            for (int i = k; i < k + sub_len; ++i) {
                for (int j = k; j < k + sub_len; ++j) {
                    ret[i][j] = sub[i - k][j - k];
                }
            }
            k += sub_len;
        }

        for (int i = 0; i < total_len + 2; ++i) {
            for (int j = 0; j < total_len + 2; ++j) {
                if (ret[i][j] == -1) {
                    ret[i][j] = u + 1;
                }
            }
        }

        return ret;
    };

    mp ans = dfs(0, -1);

    assert(adj.empty());
    // for (int i = 0; i < (int)ans.size(); ++i) {
    //     for (int j = 0; j < (int)ans[i].size(); ++j) {
    //         cerr << ans[i][j] << " ";
    //     }
    //     cerr << el;
    // }
    return ans;
}

// int main() {
//     // create_map(3, 3, {1, 2, 3}, {2, 3, 1});
//     create_map(4, 5, {1, 1, 1, 2, 2, 3}, {2, 3, 4, 3, 4, 4});
//     return 0;
// }

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