結果
問題 | No.1813 Magical Stones |
ユーザー | Nikita Skybytskyi |
提出日時 | 2022-01-14 23:16:05 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 201 ms / 2,000 ms |
コード長 | 1,907 bytes |
コンパイル時間 | 2,427 ms |
コンパイル使用メモリ | 138,568 KB |
実行使用メモリ | 20,164 KB |
最終ジャッジ日時 | 2023-08-12 22:10:14 |
合計ジャッジ時間 | 6,979 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,384 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 78 ms
18,272 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 2 ms
4,384 KB |
testcase_06 | AC | 5 ms
4,384 KB |
testcase_07 | AC | 2 ms
4,384 KB |
testcase_08 | AC | 2 ms
4,384 KB |
testcase_09 | AC | 3 ms
4,380 KB |
testcase_10 | AC | 2 ms
4,384 KB |
testcase_11 | AC | 38 ms
8,424 KB |
testcase_12 | AC | 1 ms
4,384 KB |
testcase_13 | AC | 2 ms
4,380 KB |
testcase_14 | AC | 79 ms
18,312 KB |
testcase_15 | AC | 192 ms
20,156 KB |
testcase_16 | AC | 201 ms
20,096 KB |
testcase_17 | AC | 142 ms
19,584 KB |
testcase_18 | AC | 193 ms
20,164 KB |
testcase_19 | AC | 190 ms
20,092 KB |
testcase_20 | AC | 192 ms
19,912 KB |
testcase_21 | AC | 184 ms
20,060 KB |
testcase_22 | AC | 180 ms
19,956 KB |
testcase_23 | AC | 188 ms
20,104 KB |
testcase_24 | AC | 3 ms
4,380 KB |
testcase_25 | AC | 23 ms
6,528 KB |
testcase_26 | AC | 7 ms
4,400 KB |
testcase_27 | AC | 128 ms
15,644 KB |
testcase_28 | AC | 113 ms
13,772 KB |
testcase_29 | AC | 141 ms
16,288 KB |
testcase_30 | AC | 120 ms
15,228 KB |
testcase_31 | AC | 184 ms
19,508 KB |
testcase_32 | AC | 2 ms
4,380 KB |
testcase_33 | AC | 2 ms
4,384 KB |
testcase_34 | AC | 5 ms
4,388 KB |
testcase_35 | AC | 10 ms
4,380 KB |
testcase_36 | AC | 5 ms
4,380 KB |
testcase_37 | AC | 25 ms
5,836 KB |
testcase_38 | AC | 60 ms
13,236 KB |
testcase_39 | AC | 134 ms
16,288 KB |
testcase_40 | AC | 5 ms
4,380 KB |
testcase_41 | AC | 4 ms
4,380 KB |
testcase_42 | AC | 11 ms
4,408 KB |
testcase_43 | AC | 8 ms
4,392 KB |
ソースコード
/* * Author: nskybytskyi * Time: 2022-01-13 15:08:45 */ #include <bits/stdc++.h> using namespace std; //https://cp-algorithms.com/graph/strongly-connected-components.html int main() { cin.tie(0)->sync_with_stdio(0); int n, m; cin >> n >> m; vector<vector<int>> adj(n), adj_rev(n); vector<bool> used; vector<int> order, component; while (m--) { int a, b; cin >> a >> b; --a, --b; adj[a].push_back(b); adj_rev[b].push_back(a); } function<void(int)> dfs1 = [&] (int v) -> void { used[v] = true; for (auto u: adj[v]) if (!used[u]) dfs1(u); order.push_back(v); }; function<void(int)> dfs2 = [&] (int v) -> void { used[v] = true; component.push_back(v); for (auto u : adj_rev[v]) if (!used[u]) dfs2(u); }; used.assign(n, false); for (int i = 0; i < n; ++i) if (!used[i]) dfs1(i); used.assign(n, false); reverse(order.begin(), order.end()); vector<int> roots(n, 0); vector<int> root_nodes; for (auto v: order) if (!used[v]) { dfs2(v); int root = component.front(); for (auto u : component) roots[u] = root; root_nodes.push_back(root); component.clear(); } map<int, int> scc_in, scc_out; for (int v = 0; v < n; ++v) { int root_v = roots[v]; scc_in[root_v] = scc_out[root_v] = 0; } for (int v = 0; v < n; v++) for (auto u : adj[v]) { int root_v = roots[v], root_u = roots[u]; if (root_u != root_v) { ++scc_out[root_v]; ++scc_in[root_u]; } } if (root_nodes.size() == 1) { cout << 0 << "\n"; } else { int cnt_in = 0, cnt_out = 0; for (auto [k, v] : scc_in) { if (!v) { ++cnt_in; } } for (auto [k, v] : scc_out) { if (!v) { ++cnt_out; } } cout << max(cnt_out, cnt_in) << "\n"; } return 0; }