結果
問題 | No.1553 Lovely City |
ユーザー |
![]() |
提出日時 | 2021-06-19 17:44:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 745 ms / 2,000 ms |
コード長 | 7,447 bytes |
コンパイル時間 | 2,684 ms |
コンパイル使用メモリ | 213,324 KB |
最終ジャッジ日時 | 2025-01-22 10:07:21 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define int long long#define rep(i, n) for(int (i)=0;(i)<(n);(i)++)#define rrep(i, n) for(int (i)=((n)-1);(i)>=0;(i)--)#define itn int#define miele(v) min_element(v.begin(), v.end())#define maele(v) max_element(v.begin(), v.end())#define SUM(v) accumulate(v.begin(), v.end(), 0LL)#define lb(a, key) lower_bound(a.begin(),a.end(),key)#define ub(a, key) upper_bound(a.begin(),a.end(),key)#define COUNT(a, key) count(a.begin(), a.end(), key)#define BITCOUNT(x) __builtin_popcount(x)#define pb push_back#define all(x) (x).begin(),(x).end()#define F first#define S secondusing P = pair<int, int>;using WeightedGraph = vector<vector<P>>;using UnWeightedGraph = vector<vector<int>>;using Real = long double;using Point = complex<Real>; //Point and Vector2d is the same!// p.real() or real(p) -> x軸, p.imag() or imag(p) -> y軸using Vector2d = complex<Real>;const int MOD = 1000000007;const long long INF = 1LL << 60;const double EPS = 1e-15;const double PI = 3.14159265358979323846;template<typename T>int getIndexOfLowerBound(vector<T> &v, T x) {return lower_bound(v.begin(), v.end(), x) - v.begin();}template<typename T>int getIndexOfUpperBound(vector<T> &v, T x) {return upper_bound(v.begin(), v.end(), x) - v.begin();}template<class T>inline bool chmin(T &a, T b) {if (a > b) {a = b;return true;}return false;}template<class T>inline bool chmax(T &a, T b) {if (a < b) {a = b;return true;}return false;}#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)istream &operator>>(istream &is, Point &p) {Real a, b;is >> a >> b;p = Point(a, b);return is;}template<typename T, typename U>istream &operator>>(istream &is, pair<T, U> &p_var) {is >> p_var.first >> p_var.second;return is;}template<typename T>istream &operator>>(istream &is, vector<T> &vec) {for (T &x : vec) is >> x;return is;}template<typename T, typename U>ostream &operator<<(ostream &os, pair<T, U> &pair_var) {os << pair_var.first << ' ' << pair_var.second;return os;}template<typename T>ostream &operator<<(ostream &os, vector<T> &vec) {for (int i = 0; i < vec.size(); i++)os << vec[i] << ' ';return os;}template<typename T, typename U>ostream &operator<<(ostream &os, vector<pair<T, U>> &vec) {for (int i = 0; i < vec.size(); i++)os << vec[i] << '\n';return os;}template<typename T>ostream &operator<<(ostream &os, vector<vector<T>> &df) {for (auto &vec : df) os << vec;return os;}template<typename T, typename U>ostream &operator<<(ostream &os, map<T, U> &map_var) {repi(itr, map_var) {os << *itr << ' ';itr++;itr--;}return os;}template<typename T>ostream &operator<<(ostream &os, set<T> &set_var) {repi(itr, set_var) {os << *itr << ' ';itr++;itr--;}return os;}void print() { cout << endl; }template<class Head, class... Tail>void print(Head &&head, Tail &&... tail) {cout << head;if (sizeof...(tail) != 0) cout << " ";print(forward<Tail>(tail)...);}//#https://ei1333.github.io/luzhiled/snippets/graph/strongly-connected-components.htmlお借りしますorztemplate<typename G>struct StronglyConnectedComponents {const G &g;UnWeightedGraph gg, rg;vector<int> comp, order, used;StronglyConnectedComponents(G &g) : g(g), gg(g.size()), rg(g.size()), comp(g.size(), -1), used(g.size()) {for (int i = 0; i < g.size(); i++) {for (auto e : g[i]) {gg[i].emplace_back((int) e);rg[(int) e].emplace_back(i);}}}int operator[](int k) {return comp[k];}void dfs(int idx) {if (used[idx]) return;used[idx] = true;for (int to : gg[idx]) dfs(to);order.push_back(idx);}void rdfs(int idx, int cnt) {if (comp[idx] != -1) return;comp[idx] = cnt;for (int to : rg[idx]) rdfs(to, cnt);}void build(UnWeightedGraph &t) {for (int i = 0; i < gg.size(); i++) dfs(i);reverse(begin(order), end(order));int ptr = 0;for (int i : order) if (comp[i] == -1) rdfs(i, ptr), ptr++;t.resize(ptr);for (int i = 0; i < g.size(); i++) {for (auto &to : g[i]) {int x = comp[i], y = comp[to];if (x == y) continue;t[x].push_back(y);}}}};signed main(void) { cin.tie(0); ios::sync_with_stdio(false);int n, m; cin>>n>>m;UnWeightedGraph g(n), bidirectional_g(n);rep(i, m) {int u, v; cin>>u>>v;u--, v--;g[u].pb(v);bidirectional_g[u].pb(v);bidirectional_g[v].pb(u);}StronglyConnectedComponents<UnWeightedGraph> scc(bidirectional_g);UnWeightedGraph t;scc.build(t);UnWeightedGraph newG(n);for (int i = 0; i < n; ++i) {for (int j = 0; j < g[i].size(); ++j) {if(scc[g[i][j]] == scc[i]) {newG[i].pb(g[i][j]);}}}vector<vector<int>> elementList(t.size());vector<int> deg(n);for (int i = 0; i < n; ++i) {elementList[scc[i]].pb(i);for (auto to : newG[i]) {deg[to]++;}}vector<pair<int, int>> ans;vector<int> used(t.size());// deg[i] == 0 の iを見つけたらトポロジカルソートをするfor (int i = 0; i < n; ++i) {if(!used[scc[i]]) {used[scc[i]] = true;queue<int> q;stack<int> st;for (int j = 0; j < elementList[scc[i]].size(); ++j) {if(deg[elementList[scc[i]][j]] == 0) {st.push(elementList[scc[i]][j]);q.push(elementList[scc[i]][j]);}}while(!st.empty()) {int now = st.top(); st.pop();for (int j = 0; j < newG[now].size(); ++j) {deg[newG[now][j]]--;if(deg[newG[now][j]]==0) {q.push(newG[now][j]);st.push(newG[now][j]);}}}if(q.size() == elementList[scc[i]].size()) {int now = q.front(); q.pop();while(!q.empty()) {int ne = q.front(); q.pop();ans.pb({now, ne});now = ne;}} else {int now = -1;int first = -1;int group = scc[i];for (int j = 0; j < elementList[group].size(); ++j) {int e = elementList[group][j];if(j == 0) {now = first = e;} else if(j == elementList[group].size() - 1) {ans.pb({now, e});ans.pb({e, first});} else {ans.pb({now, e});now = e;}}}}}print(ans.size());for (int i = 0; i < ans.size(); ++i) {print(ans[i].F+1, ans[i].S+1);}}