제출 #1224072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224072		moikfer	Senior Postmen (BOI14_postmen)	C++20	0 / 100	0 ms	328 KiB

postmen

#include <algorithm>
#include <vector>
#include <cassert>
#include <vector>

struct Edge {
    int from, to;
    Edge(int const _from, int const _to) : from(_from), to(_to) {}
    Edge reverse() const {
        return Edge(to, from);
    }
};

struct IndexedEdge {
    int id;
    Edge edge;
    IndexedEdge(int const _id, Edge const &_edge): id(_id), edge(_edge) {}
    IndexedEdge reverse() const {
        return IndexedEdge(id, edge.reverse());
    }
};

template<typename Ep, typename Wp>
struct WeightedEdge {
    Ep edge;
    Wp weight;
    WeightedEdge(Ep const &_edge, Wp const &_weight): edge(_edge), weight(_weight) {}
};

template<typename EdgeType, bool directed = false>
struct Graph {
    static constexpr bool is_directed = directed;
    int n, m;
    std::vector<EdgeType> edges;

    explicit Graph(int const _n): n(_n), m(0){}

    void addEdge(EdgeType const &edge) {
        edges.push_back(edge), ++m;
    }
};

template<typename Tp>
struct GridGraph {
    std::vector<std::vector<Tp>>& grid;
    int n, m;
    std::vector<std::pair<int, int>> const dirs = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
    // const vector<pair<int, int>> dirs = {
    //     {-1, -1}, {-1, 0}, {-1, 1}, {1, -1}, {1, 0}, {1, 1}, {0, -1}, {0, 1}
    // };

    GridGraph(int _n = 0, int _m = 0) : n(_n), m(_m) {}
    GridGraph(std::vector<std::vector<Tp>> const& _grid) : grid(_grid) {}

    bool inBounds(int r, int c) const {
        return 0 <= r && r < n && 0 <= c && c < m;
    }
};
#include <random>

std::mt19937& rng() {
    static std::random_device rd;
    static std::mt19937 gen(rd());
    return gen;
}

template<typename Tp>
Tp randInt(Tp a, Tp b) {
    std::uniform_int_distribution<Tp> dist(a, b);
    return dist(rng());
}

template<typename Tp>
Tp getRandomElement(std::vector<Tp> const& v) {
    return v[randInt(0, static_cast<int>(v.size()) - 1)];
}
#include <vector>

template<typename Tp>
bool checkAnElementIsIn(std::vector<Tp> const& v, Tp const& e) {
    for (Tp const& i: v) {
        if (i == e) return true;
    }
    return false;
}

struct EulerianInfo {
    bool has_eulerian_path;
    std::vector<int> vertex_path; // vertexes in eulerian walk
    std::vector<int> edge_path; // index edges in eulerian walk
};

template<bool directed>
EulerianInfo hasEulerianPath(Graph<IndexedEdge, directed> const& graph, int source = -1) {
    int n = graph.n, m = graph.m;
    assert(-1 <= source && source < n);
    if (m == 0) {
        return {true, {source == -1 ? randInt(0, n - 1) : source}, {}};
    }
    std::vector<int> vertex_path, edge_path;
    std::vector<int> deg(n);
    if constexpr (directed) {
        for (IndexedEdge const &e : graph.edges) {
            ++deg[e.edge.from], --deg[e.edge.to];
        }
        int start = -1, end = -1;
        for (int v = 0; v < n; v++) {
            if (deg[v] == 1) {
                if (start != -1)
                    return {false, {}, {}};
                start = v;
            } else if (deg[v] == -1) {
                if (end != -1)
                    return {false, {}, {}};
                end = v;
            } else if (deg[v] != 0) {
                return {false, {}, {}};
            }
        }
        if (source != -1 && start != source) {
            return {false, {}, {}};
        }
        if (source == -1) {
            if (start == -1) source = graph.edges.front().edge.from;
            else source = start;
        }
    } else {
        for (IndexedEdge const &e : graph.edges) {
            ++deg[e.edge.from], ++deg[e.edge.to];
        }
        std::vector<int> starts;
        for (int v = 0; v < n; v++) {
            if (deg[v] & 1) starts.push_back(v);
        }
        if (starts.size() != 0 and starts.size() != 2) {
            return {false, {}, {}};
        }
        if (source != -1 and starts.size() == 2 and !checkAnElementIsIn(starts, source)) {
            return {false, {}, {}};
        }
        if (source == -1) {
            if (starts.size() == 0) source = graph.edges.front().edge.from;
            else source = getRandomElement(starts);
        }
    }
    std::vector<std::vector<std::pair<int, int>>> adj(n);
    std::vector<bool> used(m);
    for (IndexedEdge const &e : graph.edges) {
        int u = e.edge.from, v = e.edge.to, id = e.id;
        adj[u].push_back({v, id});
        if constexpr (!directed) adj[v].push_back({u, id});
    }
    std::vector<std::pair<int, int>> _stack = {{source, -1}};
    while (!_stack.empty()) {
        auto &[u, id_u] = _stack.back();
        while (!adj[u].empty() && used[adj[u].back().second]) {
            adj[u].pop_back();
        }
        if (adj[u].empty()) {
            _stack.pop_back();
            vertex_path.push_back(u);
            if (id_u != -1) edge_path.push_back(id_u);
        } else {
            auto &[v, id_v] = adj[u].back();
            adj[u].pop_back();
            if (!used[id_v]) {
                used[id_v] = true;
                _stack.push_back({v, id_v});
            }
        }
    }
    if (edge_path.size() < m) {
        return {false, {}, {}};
    }
    reverse(vertex_path.begin(), vertex_path.end());
    reverse(edge_path.begin(), edge_path.end());
    return {true, vertex_path, edge_path};
}
#include <iostream>

using namespace std;

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    Graph<IndexedEdge> graph(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph.addEdge({i, {--u, --v}});
    }
    const auto [flag, vs, es] = hasEulerianPath(graph);
    vector<vector<int>> pos(n);
    assert(vs.front() == vs.back());
    for (int i = 0; i <= m; i++) {
        pos[vs[i]].push_back(i);
    }
    vector<pair<int, int>> cycles = {{0, m}};
    for (int i = 1; i < m; i++) {
        const int v = vs[i];
        int p = lower_bound(pos[v].begin(), pos[v].end(), cycles.back().second) - pos[v].begin() - 1;
        if (0 <= p and i < pos[v][p]) {
            cycles.push_back({i, pos[v][p]});
        }
    }
    reverse(cycles.begin(), cycles.end());
    for (int i = 0; i < cycles.size(); i++) {
        if (i == 0) {
            for (int j = cycles[i].first; j < cycles[i].second; j++) {
                cout << vs[j] + 1 << ' ';
            }
            cout << '\n';
        } else {
            for (int j = cycles[i].first; j < cycles[i - 1].first; j++) {
                cout << vs[j] + 1 << ' ';
            }
            for (int j = cycles[i - 1].second; j < cycles[i].second; j++) {
                cout << vs[j] + 1 << ' ';
            }
            cout << '\n';
        }
    }
    return 0;
}

• Subtask 1: 0 / 38
• Subtask 2: 0 / 17
• Subtask 3: 0 / 45