結果
| 問題 | No.2301 Namorientation |
| ユーザー |
 asaringo
|
| 提出日時 | 2023-05-13 02:46:01 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,324 bytes |
| コンパイル時間 | 2,708 ms |
| コンパイル使用メモリ | 216,624 KB |
| 最終ジャッジ日時 | 2025-02-12 23:47:29 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 10 WA * 20 |
ソースコード
#include <bits/stdc++.h>using namespace std ;#define fast_input_output ios::sync_with_stdio(false); cin.tie(nullptr);// #pragma GCC target("avx2")// #pragma GCC optimize("O3")#pragma GCC target("avx")#pragma GCC optimize("Ofast")#pragma GCC optimize("unroll-loops")typedef long long ll ;typedef long double ld ;typedef pair<ll,ll> P ;typedef tuple<ll,ll,ll> TP ;#define chmin(a,b) a = min(a,b)#define chmax(a,b) a = max(a,b)#define bit_count(x) __builtin_popcountll(x)#define gcd(a,b) __gcd(a,b)#define lcm(a,b) a / gcd(a,b) * b#define rep(i,n) for(int i = 0 ; i < n ; i++)#define rrep(i,a,b) for(int i = a ; i < b ; i++)#define repi(it,S) for(auto it = S.begin() ; it != S.end() ; it++)#define pt(a) cout << a << endl#define DEBUG(...) ; cout << #__VA_ARGS__ << endl ; for(auto x : {__VA_ARGS__}) cout << x << " " ; cout << endl ;#define DEBUG_LIST(...) cout << #__VA_ARGS__ << endl ; DEBUG_REP(__VA_ARGS__) ;#define DEBUG_REP(V) cout << "{ " ; repi(itr,V) cout << *itr << ", " ; cout << "}" << endl ;#define debug(a) cout << #a << " " << a << endl#define all(a) a.begin(), a.end()#define endl "\n"struct edge{int from;int to;int id;};template<typename Edge = edge> struct DfsTree{private:int n;vector<int> ord;vector<int> low;vector<vector<Edge>> G;vector<vector<Edge>> back_edge; // 後退辺vector<int> topological_sort;vector<Edge> bridge; // 橋vector<int> aps; // 関節点vector<vector<int>> tecc; // 連結成分iが含んでいるノードリストvector<int> tecc_idx; // ノードの連結成分番号vector<vector<int>> tecc_tree; // 連結成分を頂点、橋を辺としたグラフ(木)の隣接リストvoid init_(int n_){n = n_;ord.resize(n,-1);low.resize(n,n);G.resize(n);back_edge.resize(n);tecc_idx.resize(n,-1);}// 有向辺を張るvoid add_edge_(int u, Edge v){G[u].push_back(v);}void build_(){low_link();// two_edge_connected_component();}void low_link(){int current = 0;for(int i = 0; i < n; i++) if(ord[i] == -1) dfs_bridge(0,-1,current);}void dfs_bridge(int v, int prev, int ¤t){bool is_root = prev == -1 ? true : false;bool is_aps = false;ord[v] = current++;int count = 0;topological_sort.push_back(v);for(Edge e : G[v]){auto[from, u, id] = e;if(u == prev) continue;if(ord[u] != -1) {count++;low[v] = min(low[v],ord[u]);back_edge[v].push_back(e);continue;}dfs_bridge(u,v,current);low[v] = min(low[v], low[u]);if(!is_root && ord[v] <= low[u]) is_aps = true;if(ord[v] < low[u]) bridge.emplace_back(e);}if(is_root && count >= 2) is_aps = true;if(is_aps) aps.push_back(v);}void two_edge_connected_component(){int id = 0;int bridge_size = (int)bridge.size();tecc_tree.resize(bridge_size+1);for(int i = 0; i < n; i++) {if(tecc_idx[i] != -1) continue;tecc.push_back({});dfs(i,-1,(int)tecc.size()-1);}}void dfs(int v, int prev, int id){tecc_idx[v] = id;tecc[id].push_back(v);for(edge e : G[v]){int u = e.to;if(u == prev) continue;// すでに訪れているかif(tecc_idx[u] != -1) continue;// 橋であるかif(low[u] > ord[v] || low[v] > ord[u]) {tecc.push_back({});dfs(u,v,(int)tecc.size()-1);tecc_tree[id].push_back(tecc_idx[u]);tecc_tree[tecc_idx[u]].push_back(id);}else dfs(u,v,id);}}public:DfsTree(){}DfsTree(int n) { init_(n); }void init(int n) { init_(n); }void add_edge(int u, Edge v){ add_edge_(u, v); }void build() { build_(); }vector<Edge> get_bridge() { return bridge; } // 橋を取得vector<int> get_aps() { return aps; } // 関節点を取得vector<vector<int>> get_graph() { return G; } // グラフの取得vector<vector<Edge>> get_back_edge() { return back_edge; } // 後退辺の取得vector<vector<int>> get_all_two_edge_connected_compoonent() { return tecc; }vector<int> get_two_edge_connected_compoonent(int k) { return tecc[k]; } // 集約したグラフのノードkに含まれている元々の頂点集合int root(int v) { return tecc_idx[v]; } // 元々のノードが集約されたあとどのノードになったかvector<vector<int>> get_tecc_tree() { return tecc_tree; } // 元々のグラフを集約して得られた新しいグラフ};int n, m;bool B[202020];struct E{int to;int id;};vector<E> G[202020];pair<int,int> res[202020];pair<int,int> tmp[202020];bool used[202020];int node;void dfs(int v, int prev, int id){used[v] = true;if(id != -1){if(!B[id]) res[id] = {prev,v};else res[id] = {v,prev};}for(E e : G[v]){int u = e.to;if(u == prev) continue;if(used[u] && node != u) continue;dfs(u,v,e.id);}}int main(){cin >> n;DfsTree tree;tree.init(n);rep(i,n){int u , v ;cin >> u >> v ;u-- ; v-- ;tree.add_edge(u,{u,v,i});tree.add_edge(v,{v,u,i});G[u].push_back({v,i});G[v].push_back({u,i});tmp[i] = {u,v};}tree.build();auto bridge = tree.get_bridge();for(auto e : bridge){B[e.id] = true;node = e.from;}dfs(node,-1,-1);rep(i,n){if(res[i] == tmp[i]) cout << "->" << endl;else cout << "<-" << endl;}}