結果
問題 | No.2301 Namorientation |
ユーザー | みここ |
提出日時 | 2023-05-12 22:01:44 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 552 ms / 3,000 ms |
コード長 | 4,163 bytes |
コンパイル時間 | 911 ms |
コンパイル使用メモリ | 86,780 KB |
実行使用メモリ | 51,712 KB |
最終ジャッジ日時 | 2024-05-06 11:59:38 |
合計ジャッジ時間 | 17,095 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 2 ms
5,376 KB |
testcase_08 | AC | 3 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 2 ms
5,376 KB |
testcase_12 | AC | 300 ms
16,656 KB |
testcase_13 | AC | 274 ms
15,472 KB |
testcase_14 | AC | 542 ms
26,128 KB |
testcase_15 | AC | 338 ms
20,168 KB |
testcase_16 | AC | 435 ms
23,608 KB |
testcase_17 | AC | 305 ms
17,224 KB |
testcase_18 | AC | 480 ms
23,924 KB |
testcase_19 | AC | 244 ms
14,996 KB |
testcase_20 | AC | 444 ms
23,772 KB |
testcase_21 | AC | 348 ms
17,940 KB |
testcase_22 | AC | 437 ms
51,712 KB |
testcase_23 | AC | 429 ms
50,816 KB |
testcase_24 | AC | 364 ms
43,008 KB |
testcase_25 | AC | 290 ms
22,484 KB |
testcase_26 | AC | 381 ms
26,372 KB |
testcase_27 | AC | 543 ms
26,184 KB |
testcase_28 | AC | 526 ms
26,316 KB |
testcase_29 | AC | 552 ms
26,184 KB |
testcase_30 | AC | 540 ms
26,204 KB |
testcase_31 | AC | 532 ms
26,208 KB |
ソースコード
#include <iostream> #include <cassert> #include <queue> using namespace std; template <typename T = int> struct Graph { public: using value_type = T; struct Edge { int from, to; T cost; int id; operator int() const { return to; } }; Graph() {} Graph(int n) : n(n), m(0), g(n) {} void add_directed_edge(int from, int to, T cost = 1) { assert(0 <= from && from < n); assert(0 <= to && to < n); g[from].push_back((Edge){from, to, cost, m++}); } void add_undirected_edge(int from, int to, T cost = 1) { assert(0 <= from && from < n); assert(0 <= to && to < n); g[from].push_back((Edge){from, to, cost, m}); g[to].push_back((Edge){to, from, cost, m++}); } int size() { return n; } int edge_size() { return m; } inline const std::vector<Edge> &operator[](const int &u) const { return g[u]; } inline std::vector<Edge> &operator[](const int &u) { return g[u]; } private: int n, m; std::vector<std::vector<Edge>> g; }; template <typename GRAPH> struct LowLink { public: using EDGE = typename GRAPH::Edge; std::vector<int> articulation; std::vector<EDGE> bridge; LowLink() {} LowLink(GRAPH &g) : n(g.size()), g(g) { std::vector<int> ord(n, -1); std::vector<int> low(n, -1); int k = 0; auto dfs = [&](auto self, int u, int last_edge_id) -> void { low[u] = ord[u] = k++; int c = 0; bool is_artification = false; for (auto e : g[u]) { int v = e.to; if (e.id == last_edge_id) { continue; } if (ord[v] == -1) { c++; self(self, v, e.id); if (last_edge_id != -1 && ord[u] <= low[v]) { is_artification = true; } if (ord[u] < low[v]) { bridge.push_back(e); } low[u] = std::min(low[u], low[v]); } low[u] = std::min(low[u], ord[v]); } is_artification |= (last_edge_id == -1 && c >= 2); if (is_artification) { articulation.push_back(u); } }; for (int u = 0; u < n; u++) { if (ord[u] == -1) { dfs(dfs, u, -1); } } } private: int n; const GRAPH &g; }; int main() { int n; cin >> n; Graph<int> g(n); int a[200005], b[200005]; for (int i = 0; i < n; i++) { cin >> a[i] >> b[i]; a[i]--; b[i]--; g.add_undirected_edge(a[i], b[i]); } int r = -1; int eid = -1; LowLink<Graph<int>> low(g); { bool isbridge[200005]{0}; for (auto e : low.bridge) { isbridge[e.id] = true; } for (int i = 0; i < n; i++) { if (!isbridge[i]) { r = a[i]; eid = i; } } } bool used[200005]{0}; queue<int> que; used[r] = true; que.push(r); bool ans[200005]; ans[eid] = true; while (que.size()) { int u = que.front(); que.pop(); for (auto e : g[u]) { int v = e.to; if (used[v] || e.id == eid) { continue; } if (a[e.id] == u) { ans[e.id] = false; } else { ans[e.id] = true; } used[v] = true; que.push(v); } } for (int i = 0; i < n; i++) { if (ans[i]) { cout << "->" << endl; } else { cout << "<-" << endl; } } }