結果
問題 | No.1254 補強への架け橋 |
ユーザー | tonyu0 |
提出日時 | 2020-10-10 01:21:05 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 196 ms / 2,000 ms |
コード長 | 2,740 bytes |
コンパイル時間 | 1,382 ms |
コンパイル使用メモリ | 127,900 KB |
実行使用メモリ | 27,396 KB |
最終ジャッジ日時 | 2023-09-27 20:39:09 |
合計ジャッジ時間 | 13,580 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 1 ms
4,380 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 1 ms
4,380 KB |
testcase_07 | AC | 1 ms
4,376 KB |
testcase_08 | AC | 2 ms
4,376 KB |
testcase_09 | AC | 1 ms
4,380 KB |
testcase_10 | AC | 1 ms
4,380 KB |
testcase_11 | AC | 1 ms
4,380 KB |
testcase_12 | AC | 1 ms
4,380 KB |
testcase_13 | AC | 2 ms
4,376 KB |
testcase_14 | AC | 1 ms
4,376 KB |
testcase_15 | AC | 2 ms
4,380 KB |
testcase_16 | AC | 1 ms
4,376 KB |
testcase_17 | AC | 2 ms
4,380 KB |
testcase_18 | AC | 2 ms
4,376 KB |
testcase_19 | AC | 1 ms
4,380 KB |
testcase_20 | AC | 1 ms
4,380 KB |
testcase_21 | AC | 1 ms
4,376 KB |
testcase_22 | AC | 1 ms
4,380 KB |
testcase_23 | AC | 2 ms
4,380 KB |
testcase_24 | AC | 2 ms
4,380 KB |
testcase_25 | AC | 1 ms
4,380 KB |
testcase_26 | AC | 1 ms
4,376 KB |
testcase_27 | AC | 1 ms
4,376 KB |
testcase_28 | AC | 2 ms
4,376 KB |
testcase_29 | AC | 1 ms
4,376 KB |
testcase_30 | AC | 2 ms
4,376 KB |
testcase_31 | AC | 2 ms
4,380 KB |
testcase_32 | AC | 1 ms
4,376 KB |
testcase_33 | AC | 1 ms
4,384 KB |
testcase_34 | AC | 2 ms
4,380 KB |
testcase_35 | AC | 1 ms
4,380 KB |
testcase_36 | AC | 2 ms
4,380 KB |
testcase_37 | AC | 1 ms
4,380 KB |
testcase_38 | AC | 2 ms
4,380 KB |
testcase_39 | AC | 1 ms
4,380 KB |
testcase_40 | AC | 2 ms
4,380 KB |
testcase_41 | AC | 1 ms
4,376 KB |
testcase_42 | AC | 2 ms
4,380 KB |
testcase_43 | AC | 2 ms
4,380 KB |
testcase_44 | AC | 2 ms
4,376 KB |
testcase_45 | AC | 1 ms
4,376 KB |
testcase_46 | AC | 3 ms
4,376 KB |
testcase_47 | AC | 2 ms
4,376 KB |
testcase_48 | AC | 2 ms
4,380 KB |
testcase_49 | AC | 2 ms
4,376 KB |
testcase_50 | AC | 2 ms
4,376 KB |
testcase_51 | AC | 2 ms
4,380 KB |
testcase_52 | AC | 3 ms
4,376 KB |
testcase_53 | AC | 2 ms
4,380 KB |
testcase_54 | AC | 3 ms
4,376 KB |
testcase_55 | AC | 2 ms
4,376 KB |
testcase_56 | AC | 2 ms
4,380 KB |
testcase_57 | AC | 2 ms
4,380 KB |
testcase_58 | AC | 2 ms
4,380 KB |
testcase_59 | AC | 1 ms
4,376 KB |
testcase_60 | AC | 1 ms
4,376 KB |
testcase_61 | AC | 2 ms
4,376 KB |
testcase_62 | AC | 1 ms
4,380 KB |
testcase_63 | AC | 14 ms
5,268 KB |
testcase_64 | AC | 5 ms
4,376 KB |
testcase_65 | AC | 10 ms
4,636 KB |
testcase_66 | AC | 8 ms
4,532 KB |
testcase_67 | AC | 4 ms
4,384 KB |
testcase_68 | AC | 9 ms
4,472 KB |
testcase_69 | AC | 11 ms
4,872 KB |
testcase_70 | AC | 5 ms
4,376 KB |
testcase_71 | AC | 4 ms
4,380 KB |
testcase_72 | AC | 12 ms
4,924 KB |
testcase_73 | AC | 5 ms
4,380 KB |
testcase_74 | AC | 10 ms
4,728 KB |
testcase_75 | AC | 9 ms
4,788 KB |
testcase_76 | AC | 3 ms
4,380 KB |
testcase_77 | AC | 7 ms
4,488 KB |
testcase_78 | AC | 13 ms
5,216 KB |
testcase_79 | AC | 13 ms
5,236 KB |
testcase_80 | AC | 12 ms
5,104 KB |
testcase_81 | AC | 13 ms
5,096 KB |
testcase_82 | AC | 13 ms
4,956 KB |
testcase_83 | AC | 185 ms
23,720 KB |
testcase_84 | AC | 178 ms
23,336 KB |
testcase_85 | AC | 104 ms
15,584 KB |
testcase_86 | AC | 146 ms
20,344 KB |
testcase_87 | AC | 164 ms
22,092 KB |
testcase_88 | AC | 25 ms
6,196 KB |
testcase_89 | AC | 185 ms
23,600 KB |
testcase_90 | AC | 106 ms
16,380 KB |
testcase_91 | AC | 82 ms
13,600 KB |
testcase_92 | AC | 41 ms
8,744 KB |
testcase_93 | AC | 139 ms
19,676 KB |
testcase_94 | AC | 121 ms
18,144 KB |
testcase_95 | AC | 123 ms
18,096 KB |
testcase_96 | AC | 183 ms
22,700 KB |
testcase_97 | AC | 73 ms
12,120 KB |
testcase_98 | AC | 176 ms
22,604 KB |
testcase_99 | AC | 96 ms
15,068 KB |
testcase_100 | AC | 196 ms
24,300 KB |
testcase_101 | AC | 36 ms
8,056 KB |
testcase_102 | AC | 19 ms
5,732 KB |
testcase_103 | AC | 41 ms
8,660 KB |
testcase_104 | AC | 58 ms
10,900 KB |
testcase_105 | AC | 140 ms
19,816 KB |
testcase_106 | AC | 75 ms
13,052 KB |
testcase_107 | AC | 182 ms
23,668 KB |
testcase_108 | AC | 179 ms
23,220 KB |
testcase_109 | AC | 142 ms
19,672 KB |
testcase_110 | AC | 130 ms
17,704 KB |
testcase_111 | AC | 136 ms
19,096 KB |
testcase_112 | AC | 56 ms
10,260 KB |
testcase_113 | AC | 121 ms
17,212 KB |
testcase_114 | AC | 80 ms
12,424 KB |
testcase_115 | AC | 25 ms
6,460 KB |
testcase_116 | AC | 109 ms
14,116 KB |
testcase_117 | AC | 54 ms
10,764 KB |
testcase_118 | AC | 168 ms
22,208 KB |
testcase_119 | AC | 98 ms
14,888 KB |
testcase_120 | AC | 164 ms
21,628 KB |
testcase_121 | AC | 50 ms
9,044 KB |
testcase_122 | AC | 83 ms
13,704 KB |
testcase_123 | AC | 1 ms
4,376 KB |
testcase_124 | AC | 133 ms
27,236 KB |
testcase_125 | AC | 130 ms
27,396 KB |
ソースコード
#include <algorithm> #include <cmath> #include <iomanip> #include <iostream> #include <map> #include <numeric> #include <queue> #include <tuple> #include <vector> using namespace std; using ll = int64_t; #define rep(i, j, n) for (int i = j; i < (n); ++i) #define rrep(i, j, n) for (int i = (n)-1; j <= i; --i) template <typename T> std::ostream& operator<<(std::ostream& os, std::vector<T>& a) { os << "{"; for (size_t i = 0; i < a.size(); ++i) os << (i > 0 ? "," : "") << a[i]; return os << "}"; } [[maybe_unused]] constexpr ll MOD = 1000000007; [[maybe_unused]] constexpr int INF = 0x3f3f3f3f; [[maybe_unused]] constexpr ll INFL = 0x3f3f3f3f3f3f3f3fLL; struct Edge { int from, to; Edge(int f, int t) : from(f), to(t) {} }; using Edges = vector<Edge>; using Graph = vector<Edges>; class LowLink { public: LowLink(int n) : mGraph(n), mOrd(n), mLow(n), mUsed(n, false) {} void add_edge(int u, int v) { mGraph[u].emplace_back(u, v); mGraph[v].emplace_back(v, u); } // e(u,v)が橋 <=> ord[u] < low[v] // 頂点vが関節点 <=> ord[u] <= low[v]となるvの子uが存在 int dfs(int v, int pv, int k) { mUsed[v] = true; mOrd[v] = mLow[v] = k++; // 訪れた順 bool is_articulation = false; int cnt = 0; for (Edge nv : mGraph[v]) { if (!mUsed[nv.to]) { // まだ訪れてない ++cnt; k = dfs(nv.to, v, k); mLow[v] = min(mLow[v], mLow[nv.to]); is_articulation |= ~pv && mOrd[v] <= mLow[nv.to]; if (mOrd[v] < mLow[nv.to]) mBridges.emplace_back(minmax(v, nv.to)); } else if (nv.to != pv) { // 後退辺だったら mLow[v] = min(mLow[v], mOrd[nv.to]); } } is_articulation |= pv == -1 && cnt > 1; if (is_articulation) mArticulationPoints.push_back(v); return k; } void Init() { int k = 0; for (int i = 0; i < mGraph.size(); ++i) { if (!mUsed[i]) k = dfs(i, -1, k); } } vector<pair<int, int>> GetBridges() { return mBridges; } vector<int> GetArticulationPoints() { return mArticulationPoints; } private: Graph mGraph; vector<int> mOrd; vector<int> mLow; vector<bool> mUsed; vector<pair<int, int>> mBridges; vector<int> mArticulationPoints; }; int main() { int n, s, t; cin >> n; LowLink lowlink(n); vector<pair<int, int>> es; for (int i = 0; i < n; ++i) { cin >> s >> t; --s; --t; es.emplace_back(s, t); lowlink.add_edge(s, t); } lowlink.Init(); auto ans = lowlink.GetBridges(); map<pair<int, int>, bool> mp; for (auto p : ans) { mp[p] = true; mp[{p.second, p.first}] = true; } cout << n - ans.size() << '\n'; for (int i = 0; i < n; ++i) if (!mp[es[i]]) cout << i + 1 << " \n"[i == n - 1]; return 0; }