結果
問題 |
No.1553 Lovely City
|
ユーザー |
![]() |
提出日時 | 2024-08-07 01:47:26 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 354 ms / 2,000 ms |
コード長 | 1,617 bytes |
コンパイル時間 | 1,771 ms |
コンパイル使用メモリ | 120,552 KB |
実行使用メモリ | 29,624 KB |
最終ジャッジ日時 | 2024-08-07 01:47:38 |
合計ジャッジ時間 | 12,059 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
#include<iostream> #include<vector> #include<algorithm> using namespace std; using ll = long long; #include<atcoder/scc> #include<atcoder/dsu> int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n,m; cin>>n>>m; vector<int> u(m),v(m); atcoder::scc_graph g(n); for(int i = 0;i<m;i++){ cin>>u[i]>>v[i]; u[i]--;v[i]--; g.add_edge(u[i],v[i]); } auto use = g.scc(); vector<pair<int,int>> ans; vector<int> cnt(n,0); for(int i = 0;i<use.size();i++) for(int j:use[i]) cnt[j] = i; // for(int i = 0;i<use.size();i++){ // int m = use[i].size(); // if(m==1) continue; // for(int j = 0;j<m;j++){ // int nj = (j+1) % m; // ans.push_back(make_pair(use[i][j],use[i][nj])); // } // } int mm = use.size(); atcoder::dsu uf(mm); for(int i = 0;i<m;i++) uf.merge(cnt[u[i]],cnt[v[i]]); for(auto&now:uf.groups()){ sort(now.begin(),now.end()); bool fn = false; vector<int> can; for(int i = 0;i<now.size();i++){ int ni = now[i]; for(int j:use[ni]){ can.push_back(j); } if(use[ni].size()>1) fn = true; } for(int i = 0;i+1<can.size();i++) ans.push_back(make_pair(can[i],can[i+1])); if(fn) ans.push_back(make_pair(can.back(),can[0])); //for(int i = 0;i+1<now.size();i++) ans.push_back(make_pair(use[now[i]][0],use[now[i+1]][0])); } cout<<ans.size()<<endl; for(int i = 0;i<ans.size();i++) cout<<ans[i].first+1<<" "<<ans[i].second+1<<endl; }