結果
問題 | No.1254 補強への架け橋 |
ユーザー |
![]() |
提出日時 | 2023-08-19 10:28:58 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 127 ms / 2,000 ms |
コード長 | 9,722 bytes |
コンパイル時間 | 5,991 ms |
コンパイル使用メモリ | 344,856 KB |
実行使用メモリ | 38,692 KB |
最終ジャッジ日時 | 2024-11-29 02:03:08 |
合計ジャッジ時間 | 16,987 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 123 |
ソースコード
#include <bits/extc++.h>using namespace std;// #pragma GCC optimize("O3")// #pragma GCC optimize("unroll-loops")// using namespace __gnu_pbds;// #include <boost/multiprecision/cpp_int.hpp>// using Bint = boost::multiprecision::cpp_int;// #include <atcoder/all>// using namespace atcoder;// https://atcoder.github.io/ac-library/production/document_ja/using uint = unsigned int;using ll = long long;using ull = unsigned long long;using ld = long double;constexpr ll mod = 1e9+7;constexpr ll INF = 9'223'372'036'854'775'807/10;#define rep(i,n) for (uint i = 0; i < uint(n); ++i)#define All(a) (a).begin(),(a).end()#define PI acos(-1)vector<ll> dx = {1, 0, -1, 0, 1, 1, -1, -1};vector<ll> dy = {0, 1, 0, -1, 1, -1, 1, -1};template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }struct Edge {uint from, to;long long cost;int idx;Edge() {}Edge(uint from_, uint to_, long long cost_ = 1, int idx_ = -1) : from(from_), to(to_), cost(cost_), idx(idx_) {}bool operator<(const Edge &e) const { return cost < e.cost; }bool operator>(const Edge &e) const { return cost > e.cost; }friend ostream& operator<<(ostream& os, const Edge& e) {os << e.from << " " << e.to << " (" << e.cost << ")";return os;}operator int() const { return to; }};struct Graph {vector<vector<Edge>> G;vector<Edge> edges;Graph() {}Graph(uint n) : G(n) {}void add_edge(uint from, uint to, ll cost = 1, int idx = -1) {G[from].emplace_back(from, to, cost, idx);edges.emplace_back(from, to, cost, idx);}size_t size() const { return G.size(); }vector<Edge>& operator[](int k) { return G[k]; }friend ostream& operator<<(ostream& os, Graph& g) {for (uint i = 0; i < g.size(); i++) {for (Edge e : g[i]) {cout << e << '\n';}}return os;}};struct IoSetup {IoSetup() {cin.tie(nullptr);ios_base::sync_with_stdio(false);cout << setprecision(15) << fixed;}} iosetup;void print(const vector<string> &v) {for (string s : v) {cout << s << '\n';}}template<typename T>void print(const vector<pair<T, T>> &v, uint w = 0) {for (uint i = 0; i < (uint)v.size(); i++) {cout << right << setw(w) << v[i].first << ' ' << v[i].second << '\n';}}template<typename T>void print(const vector<T> &v, uint w = 0) {for (uint i = 0; i < (uint)v.size(); i++) {cout << right << setw(w) << v[i] << " \n"[i == (int)v.size() - 1];}}template<typename T>void print(const vector<vector<T>> &v, uint w = 0) {for (uint i = 0; i < (uint)v.size(); i++) {print(v[i], w);}}template<typename T>void print(const T& arg) {cout << arg << '\n';}template<typename T, typename... Args>void print(const T& arg, const Args&... args) {cout << arg << ' ';print(args...);}template<typename T>istream& operator>>(istream& is, vector<T>& vec) {for (auto& x : vec) is >> x;return is;}/*なもりグラフ (NamoriGraph)使い方:NamoriGraph ng(n);ng.add_edge(from, to, cost, idx); (0-indexed). 1回の add_edge で2本の辺 (無向グラフ) が追加されるng.build();ng.forest[i]: 分解された木の i 番目 (0-indexed). from, to は振り直された頂点番号 (0-indexed), cost, idx は元のグラフの辺のコストとインデックスng.loop_edges[i]: サイクルに属する i 番目 (0-indexed) の辺. from, to, cost, idx は元のグラフをコピー.ng[k]: 頂点 k について, tree_id, 振り直された木の頂点番号 id を返すng.inv(tree_id, id): tree_id の頂点 id について、元のグラフの頂点番号を返す. 特に id = 0 はサイクル上の頂点計算量:O(n)参考:https://ei1333.github.io/library/graph/others/namori-graph.hpp*/struct NamoriGraph {// g: 元のグラフ// forest: サイクルの任意の頂点を根とした木の集合// loop_edges: サイクルの辺の集合// iv: 木の番号, 頂点番号 -> 元のグラフの頂点番号// iv[i][j]: i番目の木のj番目の頂点の元のグラフの頂点番号// mark_id: 元のグラフの頂点番号 -> 木の番号// id: 元のグラフの頂点番号 -> 木の頂点番号Graph g;vector<Graph> forest;vector<Edge> loop_edges;vector<vector<int>> iv;vector<int> mark_id, id;NamoriGraph() {}NamoriGraph(uint n) : g(n) {}NamoriGraph(const Graph &g_) : g(g_) {}void add_edge(uint from, uint to, long long cost = 1, int idx = -1) {if (idx == -1) idx = (int)g.edges.size()/2; // 無向グラフなので idx = 辺の数/2g.add_edge(from, to, cost, idx);g.add_edge(to, from, cost, idx);}struct Info {// tree_id: 木の番号// id: 木の頂点番号int tree_id, id;};// 頂点 k について, tree_id, 振り直された木の頂点番号 id を返すInfo operator[](const int &k) const {return (Info){mark_id[k], id[k]};}// tree_id の頂点 id について、元のグラフの頂点番号を返す// 特に id = 0 はサイクル上の頂点int inv(int tree_id, int id_) {return iv[tree_id][id_];}void build() {int n = g.size();// deg: 次数// used: 使ったかどうかvector<int> deg(n), used(n);queue<int> que;// 次数が 1 の頂点 (先端) をキューに入れるfor (int i = 0; i < n; i++) {deg[i] = g[i].size();if (deg[i] == 1) {que.emplace(i);used[i] = true;}}while (!que.empty()) {int idx = que.front();que.pop();for (Edge &e : g[idx]) {if (used[e.to]) {continue;}// 次数が 1 の頂点の隣接頂点の次数を 1 減らすdeg[e.to]--;// 次数が 1 (サイクルに未到達)ならキューに入れるif (deg[e.to] == 1) {que.emplace(e.to);used[e.to] = true;}}}vector<int> edge_used(g.edges.size()/2 + 1);vector<int> loop;// loop を探すfor (int v = 0; v < n; v++) {// loop の点を 1 個見つけるif (!used[v]) {// それを起点に他のループを探すfor (bool update = true; update; ) {update = false;loop.emplace_back(v);// 隣接頂点が loop じゃない or すでに使っている辺ならスキップfor (Edge &e : g[v]) {if (used[e.to] || edge_used[e.idx]) { // edge_used の初期化!!!!!!!!!!!continue;}edge_used[e.idx] = true; // e.idx の辺を使用loop_edges.emplace_back(v, e.to, e.cost, e.idx); // 使った辺を追加v = e.to; // 次のループ点update = true;break;}}break;}}// 起点となる頂点が重複しているので削除loop.pop_back();mark_id.resize(n);id.resize(n);for (int i = 0; i < (int)loop.size(); i++) {int pre = loop[(i + (int)loop.size() - 1) % loop.size()]; // 前のループ点int cur = loop[i]; // 現在のループ点int nxt = loop[(i + 1) % loop.size()]; // 次のループ点int sz = 0; // 木の頂点番号// mark_id: 元のグラフの頂点番号 -> 木の番号mark_id[cur] = i;// iv[i][j]: i番目の木のj番目の頂点の元のグラフの頂点番号iv.emplace_back();iv.back().emplace_back(cur);// 木の頂点番号を振り直すid[cur] = sz++;for (Edge &e : g[cur]) {if (e.to != pre && e.to != nxt) { // サイクル上の点でなければmark_dfs(e.to, cur, i, sz); // 木の頂点番号を振り直す}}Graph tree(sz);for (Edge &e : g[cur]) {if (e.to != pre && e.to != nxt) { // サイクル上の点でなければtree[id[cur]].emplace_back(id[cur], id[e.to], e.cost, e.idx); // 木の辺を追加tree[id[e.to]].emplace_back(id[e.to], id[cur], e.cost, e.idx); // 木の辺を追加build_dfs(e.to, cur, tree); // 再帰}}forest.emplace_back(tree); // 木を追加}}// mark_dfs: 木の頂点番号を振り直す// idx: 現在の頂点// par: 親// tree_id: 木の番号// sz: 木の頂点番号void mark_dfs(int idx, int par, int tree_id, int &sz) {mark_id[idx] = tree_id; // idx の頂点は tree_id 番目の木に属するiv[tree_id].emplace_back(idx); // tree_id 番目の木の sz 番目の頂点は idxid[idx] = sz++; // idx の頂点は sz 番目の頂点for (Edge &e : g[idx]) { // idx の隣接頂点についてif (e.to != par) { // 親でなければmark_dfs(e.to, idx, tree_id, sz); // 再帰}}}void build_dfs(int idx, int par, Graph &tree) {for (Edge &e : g[idx]) { // idx の隣接頂点についてif (e.to != par) { // 親でなければtree[id[idx]].emplace_back(id[idx], id[e.to], e.cost, e.idx); // 木の辺を追加tree[id[e.to]].emplace_back(id[e.to], id[idx], e.cost, e.idx); // 木の辺を追加build_dfs(e.to, idx, tree); // 再帰}}}};void solve() {ll n;cin >> n;NamoriGraph ng(n);rep(i,n) {ll a, b;cin >> a >> b;a--; b--;ng.add_edge(a, b);}ng.build();cout << ng.loop_edges.size() << '\n';for (auto e : ng.loop_edges) {cout << e.idx+1 << ' ';}cout << '\n';}int main() {uint t = 1;// cin >> t;while (t--) {solve();}}