結果
| 問題 | No.1254 補強への架け橋 |
| ユーザー |
 ei1333333
|
| 提出日時 | 2021-04-18 02:23:16 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 145 ms / 2,000 ms |
| コード長 | 6,625 bytes |
| コンパイル時間 | 3,459 ms |
| コンパイル使用メモリ | 219,024 KB |
| 最終ジャッジ日時 | 2025-01-20 21:31:28 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 123 |
ソースコード
#include<bits/stdc++.h>using namespace std;using int64 = long long;const int mod = 1e9 + 7;// const int mod = 998244353;const int64 infll = (1LL << 62) - 1;const int inf = (1 << 30) - 1;struct IoSetup {IoSetup() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(10);cerr << fixed << setprecision(10);}} iosetup;template< typename T1, typename T2 >ostream &operator<<(ostream &os, const pair< T1, T2 > &p) {os << p.first << " " << p.second;return os;}template< typename T1, typename T2 >istream &operator>>(istream &is, pair< T1, T2 > &p) {is >> p.first >> p.second;return is;}template< typename T >ostream &operator<<(ostream &os, const vector< T > &v) {for(int i = 0; i < (int) v.size(); i++) {os << v[i] << (i + 1 != v.size() ? " " : "");}return os;}template< typename T >istream &operator>>(istream &is, vector< T > &v) {for(T &in : v) is >> in;return is;}template< typename T1, typename T2 >inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }template< typename T1, typename T2 >inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }template< typename T = int64 >vector< T > make_v(size_t a) {return vector< T >(a);}template< typename T, typename... Ts >auto make_v(size_t a, Ts... ts) {return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...));}template< typename T, typename V >typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) {t = v;}template< typename T, typename V >typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) {for(auto &e : t) fill_v(e, v);}template< typename F >struct FixPoint : F {FixPoint(F &&f) : F(forward< F >(f)) {}template< typename... Args >decltype(auto) operator()(Args &&... args) const {return F::operator()(*this, forward< Args >(args)...);}};template< typename F >inline decltype(auto) MFP(F &&f) {return FixPoint< F >{forward< F >(f)};}template< typename T = int >struct Edge {int from, to;T cost;int idx;Edge() = default;Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {}operator int() const { return to; }};template< typename T = int >struct Graph {vector< vector< Edge< T > > > g;int es;Graph() = default;explicit Graph(int n) : g(n), es(0) {}size_t size() const {return g.size();}void add_directed_edge(int from, int to, T cost = 1) {g[from].emplace_back(from, to, cost, es++);}void add_edge(int from, int to, T cost = 1) {g[from].emplace_back(from, to, cost, es);g[to].emplace_back(to, from, cost, es++);}void read(int M, int padding = -1, bool weighted = false, bool directed = false) {for(int i = 0; i < M; i++) {int a, b;cin >> a >> b;a += padding;b += padding;T c = T(1);if(weighted) cin >> c;if(directed) add_directed_edge(a, b, c);else add_edge(a, b, c);}}};template< typename T = int >using Edges = vector< Edge< T > >;/*** @brief Namori-Graph* @docs docs/namori-graph.md*/template< typename T = int >struct NamoriGraph : Graph< T > {public:using Graph< T >::Graph;using Graph< T >::g;vector< Graph< T > > forest;Edges< T > loop_edges;struct Info {int forest_id, id;};Info operator[](const int &k) const {return (Info) {mark_id[k], id[k]};}int inv(int forest_id, int k) {return iv[forest_id][k];}size_t loop_size() {return forest.size();}void build() {int n = (int) g.size();vector< int > deg(n), used(n);queue< int > que;for(int i = 0; i < n; i++) {deg[i] = (int) g[i].size();if(deg[i] == 1) {que.emplace(i);used[i] = true;}}while(not que.empty()) {int idx = que.front();que.pop();for(auto &e : g[idx]) {if(used[e.to]) {continue;}--deg[e.to];if(deg[e.to] == 1) {que.emplace(e.to);used[e.to] = true;}}}int mx = 0;for(auto &edges : g) {for(auto &e : edges) mx = max(mx, e.idx);}vector< int > edge_used(mx + 1);vector< int > loop;for(int v = 0; v < n; v++) {if(!used[v]) {for(bool update = true; update;) {update = false;loop.emplace_back(v);for(auto &e : g[v]) {if(used[e.to] or edge_used[e.idx]) {continue;}edge_used[e.idx] = true;loop_edges.emplace_back(loop.size() - 1, loop.size(), e.cost, e.idx);v = e.to;update = true;break;}}break;}}loop.pop_back();loop_edges.back().to = 0;mark_id.resize(n);id.resize(n);int ptr = 0;for(int i = 0; i < (int) loop.size(); i++) {int pre = loop[(i + loop.size() - 1) % loop.size()];int nxt = loop[(i + 1) % loop.size()];int sz = 0;mark_id[loop[i]] = ptr;iv.emplace_back();id[loop[i]] = sz++;iv.back().emplace_back(loop[i]);for(auto &e : g[loop[i]]) {if(e.to != pre and e.to != nxt) {mark_dfs(e.to, loop[i], ptr, sz);}}Graph< T > tree(sz);for(auto &e : g[loop[i]]) {if(e.to != pre and e.to != nxt) {tree.g[id[loop[i]]].emplace_back(id[loop[i]], id[e.to], e.cost, e.idx);tree.g[id[e.to]].emplace_back(id[e.to], id[loop[i]], e.cost, e.idx);build_dfs(e.to, loop[i], tree);}}forest.emplace_back(tree);}}private:vector< vector< int > > iv;vector< int > mark_id, id;void mark_dfs(int idx, int par, int k, int &l) {mark_id[idx] = k;id[idx] = l++;iv.back().emplace_back(idx);for(auto &e : g[idx]) {if(e.to != par) {mark_dfs(e.to, idx, k, l);}}}void build_dfs(int idx, int par, Graph< T > &tree) {for(auto &e : g[idx]) {if(e.to != par) {tree.g[id[idx]].emplace_back(id[idx], id[e.to], e.cost, e.idx);tree.g[id[e.to]].emplace_back(id[e.to], id[idx], e.cost, e.idx);build_dfs(e.to, idx, tree);}}}};int main() {int N;cin >> N;NamoriGraph< int > g(N);g.read(N);g.build();vector< int > ans;for(auto &e : g.loop_edges) {ans.emplace_back(e.idx + 1);}sort(begin(ans), end(ans));cout << ans.size() << "\n";cout << ans << "\n";}