結果
問題 | No.1813 Magical Stones |
ユーザー |
![]() |
提出日時 | 2024-12-01 12:26:25 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 170 ms / 2,000 ms |
コード長 | 2,126 bytes |
コンパイル時間 | 2,953 ms |
コンパイル使用メモリ | 224,532 KB |
実行使用メモリ | 19,128 KB |
最終ジャッジ日時 | 2024-12-01 12:26:34 |
合計ジャッジ時間 | 7,854 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/scc>using namespace std;using namespace atcoder;struct SCC{vector<vector<int> > groups;vector<vector<int> > graph;vector<vector<int> > dag;SCC(int n, vector<pair<int, int> >& edges){build_groups(n, edges);build_graph(n, edges);build_dag(n);}void build_groups(int n, vector<pair<int, int> >& edges){scc_graph sg(n);for(auto&[x, y] : edges){sg.add_edge(x, y);}groups = sg.scc();}void build_graph(int n, vector<pair<int, int> >& edges){graph = vector<vector<int> >(n, vector<int>({}));for(auto&[x, y] : edges){graph[x].push_back(y);}}void build_dag(int n) {int sz = (int)groups.size();dag = vector<vector<int> >(sz, vector<int>({}));vector<int> group_id(n);for (int i = 0; i < sz; ++i) {for (int x : groups[i]) {group_id[x] = i;}}for (int i = 0; i < n; i++) {for (int k : graph[i]) {int x = group_id[i], y = group_id[k];if (x != y) {dag[x].push_back(y);}}}for (vector<int>& vec : dag) {sort(vec.begin(), vec.end());vec.erase(unique(vec.begin(), vec.end()), vec.end());}}};int vec_sum(vector<bool>& vec){int ret = 0;for(int x : vec){ret += x;}return ret;}int main(){int n, m; cin >> n >> m;vector<pair<int, int> > edges(m);for(auto&[x, y] : edges){cin >> x >> y;--x, --y;}SCC scc(n, edges);int N = (int)scc.dag.size();if(N == 1){cout << 0 << endl;return 0;}vector<bool> zero_in(N, true), zero_out(N, true);for(int i = 0; i < N; ++i){for(int j : scc.dag[i]){zero_in[j] = zero_out[i] = false;}}int ans = max(vec_sum(zero_in), vec_sum(zero_out));cout << ans << endl;return 0;}