結果
問題 | No.1254 補強への架け橋 |
ユーザー |
|
提出日時 | 2020-10-09 23:12:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 302 ms / 2,000 ms |
コード長 | 2,637 bytes |
コンパイル時間 | 1,251 ms |
コンパイル使用メモリ | 86,904 KB |
最終ジャッジ日時 | 2025-01-15 05:46:28 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 123 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:31:17: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 31 | | ^ main.cpp:34:24: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 34 | auto go = [&](auto&& go, int i, int parent) -> int { | ~~~~~^~~~~~~~~~~~~~~~
ソースコード
#line 1 "main.cpp" #include <cstdio> #include <map> #include <utility> #include <vector> #line 2 "/home/user/Library/utils/macros.hpp" #define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i)) #define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i)) #define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i)) #define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i)) #define ALL(x) std::begin(x), std::end(x) #line 2 "/home/user/Library/graph/functional_graph.hpp" #include <cassert> #include <deque> #include <functional> #line 6 "/home/user/Library/graph/functional_graph.hpp" /** * @brief Namori cycle / なもり閉路 * @param g a simple connected undirected graph with |E| = |V| */ std::deque<int> get_namori_cycle(const std::vector<std::vector<int> >& g) { int n = g.size(); { // check the namori-ty int m = 0; REP (i, n) { m += g[i].size(); } assert (m == 2 * n); } std::deque<int> stk; std::vector<bool> used(n); auto go = [&](auto&& go, int i, int parent) -> int { if (used[i]) return i; stk.push_back(i); used[i] = true; for (int j : g[i]) if (j != parent) { int k = go(go, j, i); if (k != -1) return k; } assert (stk.back() == i); stk.pop_back(); used[i] = false; return -1; }; int i = go(go, 0, -1); assert (i != -1); // fails if the graph is not simple while (stk.front() != i) { stk.pop_front(); } return stk; } #line 7 "main.cpp" using namespace std; std::vector<int> solve(int n, const std::vector<std::pair<int, int> >& edges) { std::vector<std::vector<int> > g(n); std::map<std::pair<int, int>, int> lookup; REP (i, edges.size()) { auto [a, b] = edges[i]; g[a].push_back(b); g[b].push_back(a); lookup[std::make_pair(a, b)] = i; lookup[std::make_pair(b, a)] = i; } auto cycle = get_namori_cycle(g); std::vector<int> ans; REP (i, cycle.size()) { int a = cycle[i]; int b = cycle[(i + 1) % cycle.size()]; ans.push_back(lookup[std::make_pair(a, b)]); } return ans; } int main() { int n; scanf("%d", &n); std::vector<std::pair<int, int> > edges(n); REP (i, n) { int a, b; scanf("%d%d", &a, &b); -- a; -- b; edges[i] = std::make_pair(a, b); } std::vector<int> ans = solve(n, edges); printf("%d\n", (int)ans.size()); REP (i, ans.size()) { printf("%d%c", ans[i] + 1, i + 1 < ans.size() ? ' ' : '\n'); } return 0; }