結果
問題 | No.1553 Lovely City |
ユーザー |
👑 ![]() |
提出日時 | 2021-06-18 23:25:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 319 ms / 2,000 ms |
コード長 | 3,303 bytes |
コンパイル時間 | 2,827 ms |
コンパイル使用メモリ | 221,164 KB |
最終ジャッジ日時 | 2025-01-22 09:45:54 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>#pragma GCC optimize("Ofast")using namespace std;using std::cout;using std::cin;using std::endl;using ll=long long;using ld=long double;ll I=1167167167167167167;ll Q=998244353;#define rep(i,a) for (ll i=0;i<a;i++)template<class T> using _pq = priority_queue<T, vector<T>, greater<T>>;template<class T> ll LB(vector<T> &v,T a){return lower_bound(v.begin(),v.end(),a)-v.begin();}template<class T> ll UB(vector<T> &v,T a){return upper_bound(v.begin(),v.end(),a)-v.begin();}template<class T> bool chmin(T &a,const T &b){if(a>b){a=b;return 1;}else return 0;}template<class T> bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}else return 0;}template<class T> void So(vector<T> &v) {sort(v.begin(),v.end());}template<class T> void Sore(vector<T> &v) {sort(v.begin(),v.end(),[](T x,T y){return x>y;});}template<class T> void print_tate(vector<T> &v) {rep(i,v.size()) cout<<v[i]<<"\n";}void yneos(bool a){if(a) cout<<"Yes"<<"\n"; else cout<<"No"<<"\n";}#define MAX_N 200200int order[MAX_N];vector<vector<int>> G(MAX_N);vector<vector<int>> H(MAX_N);int ran[MAX_N];int r=0;void dfs(int a,int &now){if(order[a]!=-1) return ;order[a]=-2;for(auto x:G[a]){dfs(x,now);}order[a]=now;now++;}void dfs_2(int a){if(ran[a]!=-1) return ;ran[a]=r;for(auto x:H[a]) dfs_2(x);}namespace po167{struct UFtree{std::vector<int> par;std::vector<int> wei;UFtree(int n):par(n),wei(n){for(int i=0;i<n;i++){wei[i]=1,par[i]=i;}}//根っこを返すint root(int a){if(a==par[a]) return a;return par[a]=root(par[a]);}//trueなら1,falseなら0int same(int a,int b){if(root(a)==root(b)) return 1;else return 0;}//a,bが違う根っこの元なら結合する,結合したらtrueを返すbool unite(int a,int b){a=root(a),b=root(b);if(a==b) return false;if(wei[a]<wei[b]) std::swap(a,b);par[b]=a;wei[a]+=wei[b];return true;}};}using po167::UFtree;//おちこんだりもしたけれど、私はげんきです。int main() {ios::sync_with_stdio(false);cin.tie(nullptr);//inputint N,M;cin>>N>>M;UFtree A(N);rep(i,M){int a,b;cin>>a>>b;a--,b--;if(a==b) continue;G[a].push_back(b);H[b].push_back(a);A.unite(a,b);}//sccvector<pair<int,int>> ans;rep(i,N) order[i]=-1,ran[i]=-1;int now=0;rep(i,N){dfs(i,now);}int p[N];rep(i,N) p[order[i]]=i;//cout<<endl;rep(i,N){int a=p[N-1-i];if(ran[a]==-1) dfs_2(a),r++;}vector<vector<int>> F(r);map<int,int> m;map<int,vector<int>> v;rep(i,N){int a=ran[i];F[a].push_back(i);//cout<<a<<" ";}for(int i=0;i<r;i++){int a=A.root(F[i][0]);}rep(i,r){int L=F[i].size();//cout<<L<<endl;int a=A.root(F[i][0]);if(L==1) m[a]|=0;else m[a]|=1;rep(j,L) v[a].push_back(F[i][j]);}vector<int> X;for(auto x:v){auto P=x.second;int L=x.second.size();if(m[x.first]==0){//cout<<"W"<<endl;rep(j,L-1) ans.push_back({P[j],P[j+1]});}else{//cout<<"W"<<endl;rep(j,L) X.push_back(P[j]);}}int Y=X.size();//cout<<Y<<endl;rep(i,Y-1) ans.push_back({X[i],X[i+1]});if(Y>1) ans.push_back({X[Y-1],X[0]});//outputcout<<ans.size()<<"\n";rep(i,ans.size()){cout<<ans[i].first+1<<" "<<ans[i].second+1<<"\n";}return 0;}