結果
問題 | 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;}