This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A" #include <iostream> #include <numeric> #include <random> #include "library/graph/csr_graph.hpp" #include "library/util/timer.hpp" using namespace suisen; void test1() { const int n = 5; GraphBuilder<undirected_graph_tag> builder(n); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { builder.emplace_edge(i, j); } Graph g = builder.build(); for (int i = 0; i < n; ++i) { std::sort(g[i].begin(), g[i].end()); g[i].erase(std::unique(g[i].begin(), g[i].end()), g[i].end()); } for (int i = 0; i < n; ++i) { std::vector<int> actual; std::copy(g[i].begin(), g[i].end(), std::back_inserter(actual)); std::vector<int> expected(n); std::iota(expected.begin(), expected.end(), 0); assert(actual == expected); } for (int i = 0; i < n; ++i) { std::vector<int> actual; std::copy(g[i].rbegin(), g[i].rend(), std::back_inserter(actual)); std::vector<int> expected(n); std::iota(expected.rbegin(), expected.rend(), 0); assert(actual == expected); } g.shrink_to_fit(); for (int i = 0; i < n; ++i) { std::vector<int> actual; std::copy(g[i].begin(), g[i].end(), std::back_inserter(actual)); std::vector<int> expected(n); std::iota(expected.begin(), expected.end(), 0); assert(actual == expected); } for (int i = 0; i < n; ++i) { g[i].erase(std::remove_if(g[i].begin(), g[i].end(), [i](int j) { return j == i + 1; }), g[i].end()); std::vector<int> actual; std::copy(g[i].begin(), g[i].end(), std::back_inserter(actual)); std::vector<int> expected(n); std::iota(expected.begin(), expected.end(), 0); if (i != n - 1) { expected.erase(std::find(expected.begin(), expected.end(), i + 1)); } assert(actual == expected); } for (int i = 0; i < n; ++i) { if (i != n - 1) { g[i].insert(std::lower_bound(g[i].begin(), g[i].end(), i + 1), i + 1); } std::vector<int> actual; std::copy(g[i].begin(), g[i].end(), std::back_inserter(actual)); std::vector<int> expected(n); std::iota(expected.begin(), expected.end(), 0); assert(actual == expected); } for (int i = 0; i < n; ++i) { for (auto& e : g[i]) { assert(g.get_weight(e) == 1); } } } void test2() { const int n = 5; GraphBuilder<undirected_graph_tag, long long> builder(n); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { builder.emplace_edge(i, j, std::max(i, j)); } Graph g = builder.build(); for (int i = 0; i < n; ++i) { std::sort(g[i].begin(), g[i].end()); g[i].erase(std::unique(g[i].begin(), g[i].end()), g[i].end()); } for (int i = 0; i < n; ++i) { std::vector<std::pair<int, long long>> actual; std::copy(g[i].begin(), g[i].end(), std::back_inserter(actual)); std::vector<std::pair<int, long long>> expected(n); for (int j = 0; j < n; ++j) expected[j] = { j, std::max(i, j) }; assert(actual == expected); } for (int i = 0; i < n; ++i) { std::vector<std::pair<int, long long>> actual; std::copy(g[i].rbegin(), g[i].rend(), std::back_inserter(actual)); std::vector<std::pair<int, long long>> expected(n); for (int j = 0; j < n; ++j) expected[n - j - 1] = { j, std::max(i, j) }; assert(actual == expected); } g.shrink_to_fit(); for (int i = 0; i < n; ++i) { std::vector<std::pair<int, long long>> actual; std::copy(g[i].begin(), g[i].end(), std::back_inserter(actual)); std::vector<std::pair<int, long long>> expected(n); for (int j = 0; j < n; ++j) expected[j] = { j, std::max(i, j) }; assert(actual == expected); } for (int i = 0; i < n; ++i) { g[i].erase(std::remove_if(g[i].begin(), g[i].end(), [i](const std::pair<int, long long>& e) { return e.first == i + 1; }), g[i].end()); std::vector<std::pair<int, long long>> actual; std::copy(g[i].begin(), g[i].end(), std::back_inserter(actual)); std::vector<std::pair<int, long long>> expected; for (int j = 0; j < n; ++j) if (j != i + 1) expected.emplace_back(j, std::max(i, j)); assert(actual == expected); } for (int i = 0; i < n; ++i) { if (i != n - 1) g[i].insert(std::lower_bound(g[i].begin(), g[i].end(), std::pair{ i + 1, 0LL }), { i + 1, i + 1 }); std::vector<std::pair<int, long long>> actual; std::copy(g[i].begin(), g[i].end(), std::back_inserter(actual)); std::vector<std::pair<int, long long>> expected(n); for (int j = 0; j < n; ++j) expected[j] = { j, std::max(i, j) }; assert(actual == expected); } for (int i = 0; i < n; ++i) { for (auto& e : g[i]) { assert(g.get_weight(e) == std::max<int>(i, e)); } } } void test3() { auto g = Graph<void>::create_undirected_graph(3, { { 0, 1 }, { 1, 2 }, { 2, 0 } }); auto h = g; for (int i = 0; i < 3; ++i) { std::sort(h[i].begin(), h[i].end()); } if (std::vector(h[0].begin(), h[0].end()) != std::vector<int> { 1, 2 }) assert(false); if (std::vector(h[1].begin(), h[1].end()) != std::vector<int> { 0, 2 }) assert(false); if (std::vector(h[2].begin(), h[2].end()) != std::vector<int> { 0, 1 }) assert(false); } void test4() { const int n = 500000, m = 500000; std::mt19937 rng{ std::random_device{}() }; std::uniform_int_distribution<int> dist_v(0, n - 1); std::uniform_int_distribution<long long> dist_w(std::numeric_limits<long long>::min(), std::numeric_limits<long long>::max()); std::vector<std::tuple<int, int, long long>> edges; for (int i = 0; i < m; ++i) { int u = dist_v(rng); int v = dist_v(rng); long long w = dist_w(rng); edges.emplace_back(u, v, w); } Timer t; Graph g = Graph<long long>::create_directed_graph(n, edges); Graph h = Graph<long long>::create_undirected_graph(n, edges); const int swap_num = 500000; for (int i = 0; i < swap_num; ++i) { std::swap(g, h); Graph tmp = std::move(g); g = std::move(h); h = std::move(tmp); } assert(t.elapsed() <= 1000); } int main() { test1(); test2(); test3(); test4(); std::cout << "Hello World" << std::endl; return 0; }
#line 1 "test/src/graph/csr_graph/dummy.test.cpp" #define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A" #include <iostream> #include <numeric> #include <random> #line 1 "library/graph/csr_graph.hpp" #include <algorithm> #include <cassert> #include <limits> #include <optional> #include <type_traits> #include <tuple> #include <utility> #include <vector> namespace suisen { namespace internal::csr_graph { struct graph_base_tag {}; } struct directed_graph_tag : internal::csr_graph::graph_base_tag {}; struct undirected_graph_tag : internal::csr_graph::graph_base_tag {}; template <typename T> struct is_graph_tag { static constexpr bool value = std::is_base_of_v<internal::csr_graph::graph_base_tag, T>; }; template <typename T> constexpr bool is_graph_tag_v = is_graph_tag<T>::value; template <typename WeightType = void> struct Graph { template <typename GraphTag, typename, std::enable_if_t<is_graph_tag_v<GraphTag>, std::nullptr_t>> friend struct GraphBuilder; using weight_type = WeightType; static constexpr bool weighted = std::negation_v<std::is_same<weight_type, void>>; using weight_type_or_1 = std::conditional_t<weighted, weight_type, int>; using input_edge_type = std::conditional_t<weighted, std::tuple<int, int, weight_type>, std::pair<int, int>>; private: using internal_edge_type = std::conditional_t<weighted, std::pair<int, weight_type>, int>; struct Edge : public internal_edge_type { using internal_edge_type::internal_edge_type; operator int() const { return std::get<0>(*this); } }; public: using edge_type = std::conditional_t<weighted, Edge, int>; private: struct AdjacentList { friend struct Graph; using value_type = edge_type; using iterator = typename std::vector<value_type>::iterator; using const_iterator = typename std::vector<value_type>::const_iterator; using reverse_iterator = typename std::vector<value_type>::reverse_iterator; using const_reverse_iterator = typename std::vector<value_type>::const_reverse_iterator; AdjacentList() = default; int size() const { return _siz; } bool empty() const { return _siz == 0; } int capacity() const { return _cap; } value_type& operator[](int i) { return *(begin() + i); } const value_type& operator[](int i) const { return *(cbegin() + i); } value_type& at(uint32_t i) { assert(i < _siz); return *(begin() + i); } const value_type& at(uint32_t i) const { assert(i < _siz); return *(cbegin() + i); } value_type* data() { return _g->_edges.data() + _offset; } const value_type* data() const { return _g->_edges.data() + _offset; } iterator begin() const { return _g->_edges.begin() + _offset; } iterator end() const { return begin() + _siz; } const_iterator cbegin() const { return _g->_edges.cbegin() + _offset; } const_iterator cend() const { return cbegin() + _siz; } reverse_iterator rbegin() const { return _g->_edges.rbegin() + (_g->_edges.size() - (_offset + _siz)); } reverse_iterator rend() const { return rbegin() + _siz; } const_reverse_iterator crbegin() const { return _g->_edges.crbegin() + (_g->_edges.size() - (_offset + _siz)); } const_reverse_iterator crend() const { return crbegin() + _siz; } void erase(const_iterator pos) { erase(pos, std::next(pos)); } void erase(const_iterator first, const_iterator last) { const int num = last - first, k = first - cbegin(); assert(num >= 0); if (num == 0) return; assert(0 <= k and k <= _siz - num); std::move(begin() + k + num, end(), begin() + k); _siz -= num; } void pop_back() { assert(_siz); --_siz; } void clear() { _siz = 0; } const value_type& back() const { return *--cend(); } value_type& back() { return *--end(); } const value_type& front() const { return *cbegin(); } value_type& front() { return *begin(); } void push_back(const value_type& x) { ++_siz; assert(_siz <= _cap); back() = x; } template <typename ...Args> void emplace_back(Args &&...args) { ++_siz; assert(_siz <= _cap); back() = value_type(std::forward<Args>(args)...); } void insert(const_iterator pos, const value_type& x) { emplace(pos, x); } void insert(const_iterator pos, int num, const value_type& x) { const int k = pos - cbegin(); assert(0 <= k and k <= _siz); std::fill(begin() + k, shift_back(begin() + k, num), x); } template <class RandomAccessIterator> auto insert(const_iterator pos, RandomAccessIterator first, RandomAccessIterator last) -> decltype(*first++, last - first, void()) { const int num = last - first, k = pos - cbegin(); assert(0 <= k and k <= _siz); shift_back(begin() + k, num); std::copy(first, last, begin() + k); } void insert(const_iterator pos, std::initializer_list<value_type> il) { insert(pos, il.begin(), il.end()); } template <typename ...Args> void emplace(const_iterator pos, Args &&...args) { const int k = pos - cbegin(); assert(0 <= k and k <= _siz); *--shift_back(begin() + k) = value_type(std::forward<Args>(args)...); } private: mutable Graph* _g; int _cap; int _offset; int _siz; iterator shift_back(iterator pos, int num = 1) { _siz += num; assert(_siz <= _cap); return std::move_backward(pos, end() - num, end()); } }; public: using adjacent_list = AdjacentList; Graph() = default; template <typename GraphTag, std::enable_if_t<is_graph_tag_v<GraphTag>, std::nullptr_t> = nullptr> Graph(const int n, const std::vector<input_edge_type>& edges, GraphTag, std::vector<int> cap = {}) : _n(n), _adj(_n) { static constexpr bool undirected = std::is_same_v<undirected_graph_tag, GraphTag>; for (const auto& e : edges) { const int u = std::get<0>(e); ++_adj[u]._siz; if constexpr (undirected) { const int v = std::get<1>(e); ++_adj[v]._siz; } } if (cap.empty()) cap.resize(_n, std::numeric_limits<int>::max()); int edge_num = 0; for (int i = 0; i < _n; ++i) { _adj[i]._g = this; _adj[i]._cap = std::min(_adj[i]._siz, cap[i]); _adj[i]._offset = edge_num; edge_num += _adj[i]._siz; } _edges.resize(edge_num); std::vector<typename std::vector<edge_type>::iterator> ptr(_n); for (int i = 0; i < _n; ++i) ptr[i] = _adj[i].begin(); for (const auto& e : edges) { const int u = std::get<0>(e); const int v = std::get<1>(e); if constexpr (weighted) { const weight_type& w = std::get<2>(e); *ptr[u]++ = { v, w }; if constexpr (undirected) *ptr[v]++ = { u, w }; } else { *ptr[u]++ = v; if constexpr (undirected) *ptr[v]++ = u; } } } Graph(const std::vector<std::vector<edge_type>>& g) : Graph(g.size(), make_edges(g), directed_graph_tag{}) {} static Graph create_directed_graph(const int n, const std::vector<input_edge_type>& edges, const std::vector<int>& cap = {}) { return Graph(n, edges, directed_graph_tag{}, cap); } static Graph create_undirected_graph(const int n, const std::vector<input_edge_type>& edges, const std::vector<int>& cap = {}) { return Graph(n, edges, undirected_graph_tag{}, cap); } adjacent_list& operator[](int i) { _adj[i]._g = this; return _adj[i]; } const adjacent_list& operator[](int i) const { _adj[i]._g = const_cast<Graph*>(this); return _adj[i]; } int size() const { return _n; } void shrink_to_fit() { int edge_num = 0; for (const auto& l : _adj) edge_num += l.size(); std::vector<edge_type> new_edges(edge_num); auto it = new_edges.begin(); for (int i = 0; i < _n; ++i) { int nl = it - new_edges.begin(); it = std::move(_adj[i].begin(), _adj[i].end(), it); _adj[i]._offset = nl; _adj[i]._cap = _adj[i]._siz; } _edges.swap(new_edges); } static weight_type_or_1 get_weight(const edge_type& edge) { if constexpr (weighted) return std::get<1>(edge); else return 1; } Graph reversed(const std::vector<int>& cap = {}) const { std::vector<input_edge_type> edges; for (int i = 0; i < _n; ++i) { for (const auto& edge : (*this)[i]) { if constexpr (weighted) edges.emplace_back(std::get<0>(edge), i, std::get<1>(edge)); else edges.emplace_back(edge, i); } } return Graph(_n, std::move(edges), directed_graph_tag{}, cap); } struct DFSTree { std::vector<int> par; std::vector<int> pre_ord, pst_ord; Graph tree, back; }; DFSTree dfs_tree(int start = 0) const { std::vector<input_edge_type> tree_edge, back_edge; std::vector<int> pre(_n), pst(_n); auto pre_it = pre.begin(), pst_it = pst.begin(); std::vector<int> eid(_n, -1), par(_n, -2); std::vector<std::optional<weight_type_or_1>> par_w(_n, std::nullopt); for (int i = 0; i < _n; ++i) { int cur = (start + i) % _n; if (par[cur] != -2) continue; par[cur] = -1; while (cur >= 0) { ++eid[cur]; if (eid[cur] == 0) *pre_it++ = cur; if (eid[cur] == _adj[cur].size()) { *pst_it++ = cur; cur = par[cur]; } else { const auto &e = _adj[cur][eid[cur]]; weight_type_or_1 w = get_weight(e); int nxt = e; if (par[nxt] == -2) { tree_edge.emplace_back(make_edge(cur, e)); par[nxt] = cur; par_w[nxt] = std::move(w); cur = nxt; } else if (eid[nxt] != _adj[nxt].size()) { if (par[cur] != nxt or par_w[cur] != w or not std::exchange(par_w[cur], std::nullopt).has_value()) { back_edge.emplace_back(make_edge(cur, e)); } } } } } Graph tree = create_directed_graph(_n, tree_edge); Graph back = create_directed_graph(_n, back_edge); return DFSTree{ std::move(par), std::move(pre), std::move(pst), std::move(tree), std::move(back) }; } private: int _n; std::vector<adjacent_list> _adj; std::vector<edge_type> _edges; static std::vector<input_edge_type> make_edges(const std::vector<std::vector<edge_type>>& g) { const int n = g.size(); std::vector<input_edge_type> edges; for (int i = 0; i < n; ++i) for (const auto& e : g[i]) { edges.emplace_back(make_edge(i, e)); } return edges; } static input_edge_type make_edge(int i, const edge_type& e) { if constexpr (weighted) return { i, std::get<0>(e), std::get<1>(e) }; else return { i, e }; } }; template <typename GraphTag> Graph(int, std::vector<std::pair<int, int>>, GraphTag, std::vector<int> = {})->Graph<void>; template <typename WeightType, typename GraphTag> Graph(int, std::vector<std::tuple<int, int, WeightType>>, GraphTag, std::vector<int> = {})->Graph<WeightType>; Graph(std::vector<std::vector<int>>)->Graph<void>; template <typename WeightType> Graph(std::vector<std::vector<std::pair<int, WeightType>>>)->Graph<WeightType>; template <typename GraphTag, typename WeightType = void, std::enable_if_t<is_graph_tag_v<GraphTag>, std::nullptr_t> = nullptr> struct GraphBuilder { using graph_tag = GraphTag; using weight_type = WeightType; using edge_type = typename Graph<weight_type>::input_edge_type; GraphBuilder(int n = 0) : _n(n) {} void add_edge(const edge_type& edge) { check_not_moved(); _edges.push_back(edge); } template <typename ...Args> void emplace_edge(Args &&...args) { check_not_moved(); _edges.emplace_back(std::forward<Args>(args)...); } template <typename EdgeContainer, std::enable_if_t<std::is_constructible_v<edge_type, typename EdgeContainer::value_type>, std::nullptr_t> = nullptr> void add_edges(const EdgeContainer& edges) { for (const auto& edge : edges) add_edge(edge); } template <bool move_edges = true> Graph<weight_type> build() { if constexpr (move_edges) { _moved = true; return Graph<weight_type>(_n, std::move(_edges), graph_tag{}); } else { return Graph<weight_type>(_n, _edges, graph_tag{}); } } Graph<weight_type> build_without_move() { return build<false>(); } static Graph<weight_type> build(const int n, const std::vector<edge_type>& edges) { GraphBuilder builder(n); builder.add_edges(edges); return builder.build(); } private: int _n; std::vector<edge_type> _edges; bool _moved = false; void check_not_moved() { if (not _moved) return; std::cerr << "[\033[31mERROR\033[m] Edges are already moved. If you want to add edges after calling build() and build another graph, you should use build_without_move() instead." << std::endl; assert(false); } }; template <typename WeightType = void> using DirectedGraphBuilder = GraphBuilder<directed_graph_tag, WeightType>; template <typename WeightType = void> using UndirectedGraphBuilder = GraphBuilder<undirected_graph_tag, WeightType>; template <typename Weight, std::enable_if_t<std::negation_v<std::is_same<Weight, void>>, std::nullptr_t> = nullptr> using WeightedGraph = Graph<Weight>; using UnweightedGraph = Graph<void>; template <typename T> struct is_weighted_graph { static constexpr bool value = false; }; template <typename WeightType> struct is_weighted_graph<Graph<WeightType>> { static constexpr bool value = Graph<WeightType>::weighted; }; template <typename T> constexpr bool is_weighted_graph_v = is_weighted_graph<T>::value; template <typename T> struct is_unweighted_graph { static constexpr bool value = false; }; template <typename WeightType> struct is_unweighted_graph<Graph<WeightType>> { static constexpr bool value = not Graph<WeightType>::weighted; }; template <typename T> constexpr bool is_unweighted_graph_v = is_unweighted_graph<T>::value; } // namespace suisen #line 1 "library/util/timer.hpp" #include <chrono> namespace suisen { struct Timer { using minutes_t = std::chrono::minutes; using seconds_t = std::chrono::seconds; using milliseconds_t = std::chrono::milliseconds; using microseconds_t = std::chrono::microseconds; using nanoseconds_t = std::chrono::nanoseconds; Timer() { start(); } void start() { _start = std::chrono::system_clock::now(); } template <typename TimeUnit = std::chrono::milliseconds> double elapsed() const { return std::chrono::duration_cast<TimeUnit>(std::chrono::system_clock::now() - _start).count(); } template <typename TimeUnit = std::chrono::milliseconds, typename Proc> static double measure(Proc &&proc) { Timer timer; proc(); return timer.elapsed<TimeUnit>(); } private: decltype(std::chrono::system_clock::now()) _start; }; } // namespace suisen #line 9 "test/src/graph/csr_graph/dummy.test.cpp" using namespace suisen; void test1() { const int n = 5; GraphBuilder<undirected_graph_tag> builder(n); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { builder.emplace_edge(i, j); } Graph g = builder.build(); for (int i = 0; i < n; ++i) { std::sort(g[i].begin(), g[i].end()); g[i].erase(std::unique(g[i].begin(), g[i].end()), g[i].end()); } for (int i = 0; i < n; ++i) { std::vector<int> actual; std::copy(g[i].begin(), g[i].end(), std::back_inserter(actual)); std::vector<int> expected(n); std::iota(expected.begin(), expected.end(), 0); assert(actual == expected); } for (int i = 0; i < n; ++i) { std::vector<int> actual; std::copy(g[i].rbegin(), g[i].rend(), std::back_inserter(actual)); std::vector<int> expected(n); std::iota(expected.rbegin(), expected.rend(), 0); assert(actual == expected); } g.shrink_to_fit(); for (int i = 0; i < n; ++i) { std::vector<int> actual; std::copy(g[i].begin(), g[i].end(), std::back_inserter(actual)); std::vector<int> expected(n); std::iota(expected.begin(), expected.end(), 0); assert(actual == expected); } for (int i = 0; i < n; ++i) { g[i].erase(std::remove_if(g[i].begin(), g[i].end(), [i](int j) { return j == i + 1; }), g[i].end()); std::vector<int> actual; std::copy(g[i].begin(), g[i].end(), std::back_inserter(actual)); std::vector<int> expected(n); std::iota(expected.begin(), expected.end(), 0); if (i != n - 1) { expected.erase(std::find(expected.begin(), expected.end(), i + 1)); } assert(actual == expected); } for (int i = 0; i < n; ++i) { if (i != n - 1) { g[i].insert(std::lower_bound(g[i].begin(), g[i].end(), i + 1), i + 1); } std::vector<int> actual; std::copy(g[i].begin(), g[i].end(), std::back_inserter(actual)); std::vector<int> expected(n); std::iota(expected.begin(), expected.end(), 0); assert(actual == expected); } for (int i = 0; i < n; ++i) { for (auto& e : g[i]) { assert(g.get_weight(e) == 1); } } } void test2() { const int n = 5; GraphBuilder<undirected_graph_tag, long long> builder(n); for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { builder.emplace_edge(i, j, std::max(i, j)); } Graph g = builder.build(); for (int i = 0; i < n; ++i) { std::sort(g[i].begin(), g[i].end()); g[i].erase(std::unique(g[i].begin(), g[i].end()), g[i].end()); } for (int i = 0; i < n; ++i) { std::vector<std::pair<int, long long>> actual; std::copy(g[i].begin(), g[i].end(), std::back_inserter(actual)); std::vector<std::pair<int, long long>> expected(n); for (int j = 0; j < n; ++j) expected[j] = { j, std::max(i, j) }; assert(actual == expected); } for (int i = 0; i < n; ++i) { std::vector<std::pair<int, long long>> actual; std::copy(g[i].rbegin(), g[i].rend(), std::back_inserter(actual)); std::vector<std::pair<int, long long>> expected(n); for (int j = 0; j < n; ++j) expected[n - j - 1] = { j, std::max(i, j) }; assert(actual == expected); } g.shrink_to_fit(); for (int i = 0; i < n; ++i) { std::vector<std::pair<int, long long>> actual; std::copy(g[i].begin(), g[i].end(), std::back_inserter(actual)); std::vector<std::pair<int, long long>> expected(n); for (int j = 0; j < n; ++j) expected[j] = { j, std::max(i, j) }; assert(actual == expected); } for (int i = 0; i < n; ++i) { g[i].erase(std::remove_if(g[i].begin(), g[i].end(), [i](const std::pair<int, long long>& e) { return e.first == i + 1; }), g[i].end()); std::vector<std::pair<int, long long>> actual; std::copy(g[i].begin(), g[i].end(), std::back_inserter(actual)); std::vector<std::pair<int, long long>> expected; for (int j = 0; j < n; ++j) if (j != i + 1) expected.emplace_back(j, std::max(i, j)); assert(actual == expected); } for (int i = 0; i < n; ++i) { if (i != n - 1) g[i].insert(std::lower_bound(g[i].begin(), g[i].end(), std::pair{ i + 1, 0LL }), { i + 1, i + 1 }); std::vector<std::pair<int, long long>> actual; std::copy(g[i].begin(), g[i].end(), std::back_inserter(actual)); std::vector<std::pair<int, long long>> expected(n); for (int j = 0; j < n; ++j) expected[j] = { j, std::max(i, j) }; assert(actual == expected); } for (int i = 0; i < n; ++i) { for (auto& e : g[i]) { assert(g.get_weight(e) == std::max<int>(i, e)); } } } void test3() { auto g = Graph<void>::create_undirected_graph(3, { { 0, 1 }, { 1, 2 }, { 2, 0 } }); auto h = g; for (int i = 0; i < 3; ++i) { std::sort(h[i].begin(), h[i].end()); } if (std::vector(h[0].begin(), h[0].end()) != std::vector<int> { 1, 2 }) assert(false); if (std::vector(h[1].begin(), h[1].end()) != std::vector<int> { 0, 2 }) assert(false); if (std::vector(h[2].begin(), h[2].end()) != std::vector<int> { 0, 1 }) assert(false); } void test4() { const int n = 500000, m = 500000; std::mt19937 rng{ std::random_device{}() }; std::uniform_int_distribution<int> dist_v(0, n - 1); std::uniform_int_distribution<long long> dist_w(std::numeric_limits<long long>::min(), std::numeric_limits<long long>::max()); std::vector<std::tuple<int, int, long long>> edges; for (int i = 0; i < m; ++i) { int u = dist_v(rng); int v = dist_v(rng); long long w = dist_w(rng); edges.emplace_back(u, v, w); } Timer t; Graph g = Graph<long long>::create_directed_graph(n, edges); Graph h = Graph<long long>::create_undirected_graph(n, edges); const int swap_num = 500000; for (int i = 0; i < swap_num; ++i) { std::swap(g, h); Graph tmp = std::move(g); g = std::move(h); h = std::move(tmp); } assert(t.elapsed() <= 1000); } int main() { test1(); test2(); test3(); test4(); std::cout << "Hello World" << std::endl; return 0; }