結果
| 問題 | No.1254 補強への架け橋 |
| ユーザー |
 KoD
|
| 提出日時 | 2020-10-09 21:31:13 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 207 ms / 2,000 ms |
| コード長 | 6,271 bytes |
| コンパイル時間 | 4,519 ms |
| コンパイル使用メモリ | 142,364 KB |
| 最終ジャッジ日時 | 2025-01-15 04:02:17 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 123 |
ソースコード
#line 1 "main.cpp"/*** @title Template*/#include <iostream>#include <algorithm>#include <utility>#include <numeric>#include <vector>#include <array>#include <cassert>#include <map>#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/chmin_chmax.cpp"template <class T, class U>constexpr bool chmin(T &lhs, const U &rhs) {if (lhs > rhs) { lhs = rhs; return true; }return false;}template <class T, class U>constexpr bool chmax(T &lhs, const U &rhs) {if (lhs < rhs) { lhs = rhs; return true; }return false;}/*** @title Chmin/Chmax*/#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp"class range {public:class iterator {private:int64_t M_position;public:constexpr iterator(int64_t position) noexcept: M_position(position) { }constexpr void operator ++ () noexcept { ++M_position; }constexpr bool operator != (iterator other) const noexcept { return M_position != other.M_position; }constexpr int64_t operator * () const noexcept { return M_position; }};class reverse_iterator {private:int64_t M_position;public:constexpr reverse_iterator(int64_t position) noexcept: M_position(position) { }constexpr void operator ++ () noexcept { --M_position; }constexpr bool operator != (reverse_iterator other) const noexcept { return M_position != other.M_position; }constexpr int64_t operator * () const noexcept { return M_position; }};private:const iterator M_first, M_last;public:constexpr range(int64_t first, int64_t last) noexcept: M_first(first), M_last(std::max(first, last)) { }constexpr iterator begin() const noexcept { return M_first; }constexpr iterator end() const noexcept { return M_last; }constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator(*M_last - 1); }constexpr reverse_iterator rend() const noexcept { return reverse_iterator(*M_first - 1); }};/*** @title Range*/#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/fix_point.cpp"#line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/other/fix_point.cpp"template <class Func>struct fix_point_impl: private Func {explicit constexpr fix_point_impl(Func &&func): Func(std::forward<Func>(func)) { }template <class... Args>constexpr decltype(auto) operator () (Args &&... args) const {return Func::operator()(*this, std::forward<Args>(args)...);}};template <class Func>constexpr decltype(auto) fix_point(Func &&func) {return fix_point_impl<Func>(std::forward<Func>(func));}/*** @title Lambda Recursion*/#line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/graph/union_find.cpp"#include <cstddef>#line 7 "/Users/kodamankod/Desktop/cpp_programming/Library/graph/union_find.cpp"class union_find {public:using size_type = size_t;private:class node_type {public:size_type parent, size;node_type(size_type parent):parent(parent), size(1){ }};size_type M_components;std::vector<node_type> M_forest;public:union_find() = default;explicit union_find(const size_type size) { initialize(size); }void initialize(const size_type size) {clear();M_components = size;M_forest.reserve(size);for (size_type index = 0; index < size; ++index) {M_forest.emplace_back(index);}}size_type find_parent(const size_type node) {assert(node < size());size_type &parent = M_forest[node].parent;if (node == parent) return node;return parent = find_parent(parent);}size_type count_components() const {return M_components;}size_type component_size(const size_type node) {assert(node < size());return M_forest[find_parent(node)].size;}bool unite(size_type node1, size_type node2) {assert(node1 < size());assert(node2 < size());node1 = find_parent(node1);node2 = find_parent(node2);if (node1 == node2) return false;if (M_forest[node1].size < M_forest[node2].size) {std::swap(node1, node2);}M_forest[node1].size += M_forest[node2].size;M_forest[node2].parent = node1;--M_components;return true;}bool same_component(const size_type node1, const size_type node2) {assert(node1 < size());assert(node2 < size());return find_parent(node1) == find_parent(node2);}size_type size() const {return M_forest.size();}bool empty() const {return M_forest.empty();}void clear() {M_components = 0;M_forest.clear();M_forest.shrink_to_fit();}};/*** @title Disjoint Set Union*/#line 19 "main.cpp"using i32 = std::int32_t;using i64 = std::int64_t;using u32 = std::uint32_t;using u64 = std::uint64_t;using isize = std::ptrdiff_t;using usize = std::size_t;constexpr i32 inf32 = (i32(1) << 30) - 1;constexpr i64 inf64 = (i64(1) << 62) - 1;int main() {usize N;std::cin >> N;std::vector<usize> A(N), B(N);std::map<std::pair<usize, usize>, usize> Id;for (auto i: range(0, N)) {std::cin >> A[i] >> B[i];--A[i]; --B[i];Id[std::minmax(A[i], B[i])] = i;}std::vector<std::vector<usize>> graph(N);union_find dsu(N);usize st, en;for (auto i: range(0, N)) {if (dsu.unite(A[i], B[i])) {graph[A[i]].push_back(B[i]);graph[B[i]].push_back(A[i]);}else {st = A[i];en = B[i];}}std::vector<usize> parent(N), depth(N);fix_point([&](auto dfs, usize u, usize p, usize d) -> void {parent[u] = p;depth[u] = d;for (auto v: graph[u]) {if (v != p) {dfs(v, u, d + 1);}}})(0, 0, 0);std::vector<usize> ans;ans.push_back(Id[std::minmax(st, en)]);while (st != en) {if (depth[st] > depth[en]) {ans.push_back(Id[std::minmax(st, parent[st])]);st = parent[st];}else {ans.push_back(Id[std::minmax(en, parent[en])]);en = parent[en];}}std::cout << ans.size() << '\n';std::sort(ans.begin(), ans.end());for (auto i: range(0, ans.size())) {std::cout << ans[i] + 1 << (i + 1 == (isize) ans.size() ? '\n' : ' ');}return 0;}