結果
問題 |
No.2301 Namorientation
|
ユーザー |
|
提出日時 | 2023-10-28 04:42:17 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,953 bytes |
コンパイル時間 | 2,169 ms |
コンパイル使用メモリ | 213,164 KB |
最終ジャッジ日時 | 2025-02-17 16:33:09 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 6 WA * 24 |
ソースコード
#include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < n; ++i) typedef long long ll; using namespace std; struct Namori { vector<vector<int>> forest; vector<int> loop; Namori(vector<vector<int>> &G) { int N = G.size(); vector<int> deg(N); forest.resize(N); rep(i, N) deg[i] = G[i].size(); queue<int> q; vector<bool> seen(N); rep(i, N) { if (deg[i] == 1) { q.emplace(i); seen[i] = true; } } while (!q.empty()) { int u = q.front(); q.pop(); for (int v : G[u]) { if (seen[v]) continue; deg[v]--; forest[u].emplace_back(v); forest[v].emplace_back(u); if (deg[v] == 1) { q.emplace(v); seen[v] = true; } } } rep(i, N) { if (!seen[i]) loop.emplace_back(i); } } }; int main() { cin.tie(0)->sync_with_stdio(0); int N; cin >> N; vector<vector<int>> G(N); map<pair<int, int>, int> ids; rep(i, N) { int u, v; cin >> u >> v; u--, v--; ids[{u, v}] = i; ids[{v, u}] = i + N; G[u].emplace_back(v); G[v].emplace_back(u); } Namori g(G); vector<int> ans(2 * N); rep(i, g.loop.size()) { int u = g.loop[i], v = g.loop[(i + 1) % g.loop.size()]; ans[ids[{u, v}]] = 1; if (g.forest[u].size() == 0) continue; reverse(g.forest[u].begin(), g.forest[u].end()); g.forest[u].emplace_back(u); rep(j, g.forest[u].size() - 1) { ans[ids[{g.forest[u][j], g.forest[u][j + 1]}]] = 1; } } rep(i, N) { if (ans[i] == 1) cout << "->\n"; else cout << "<-\n"; } return 0; }