Submission #1224120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224120		moikfer	Senior Postmen (BOI14_postmen)	C++20	100 / 100	220 ms	48912 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 <stack>
#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<bool> used(n);
    stack<int> _stack;
    for(int i = 0; i <= m; i++){
   		if (used[vs[i]]) {
   		    vector<int> path;
   			while (!_stack.empty() && _stack.top() != vs[i]) {
   				int v = _stack.top();
   				_stack.pop();
   				path.push_back(v);
   				used[v] = false;
   			}
   			path.push_back(vs[i]);
   			reverse(path.begin(), path.end());
   			for (const int &v: path) {
   				cout << v + 1 << ' ';
   			}
   			cout << '\n';
   		} else {
   		    _stack.push(vs[i]);
   			used[vs[i]] = true;
   		}
    }
    return 0;
}

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