結果
問題 |
No.2301 Namorientation
|
ユーザー |
![]() |
提出日時 | 2023-05-13 11:59:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 528 ms / 3,000 ms |
コード長 | 3,933 bytes |
コンパイル時間 | 1,163 ms |
コンパイル使用メモリ | 120,716 KB |
最終ジャッジ日時 | 2025-02-13 00:00:50 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <queue> #include <set> #include <random> #include <iomanip> #include <string> #include <cmath> #include <complex> using namespace std; typedef long long ll; #define rep(i, n) for(int i = 0; i < (n); i++) template<class T> using vi = vector<T>; template<class T> using vii = vector<vi<T>>; template<class T> using viii = vector<vii<T>>; template<class T> using viiii = vector<viii<T>>; using P = pair<ll, int>; void chmin(ll & x, ll y) { x = min(x, y); } void chmax(ll& x, ll y) { x = max(x, y); } struct mint { const long long mod = 998244353; long long x; mint(long long x_ = 0) : x((x_% mod + mod) % mod) {} mint& operator+=(const mint& other) { x += other.x; if (x >= mod) x -= mod; return *this; } mint& operator-=(const mint& other) { x -= other.x; if (x < 0) x += mod; return *this; } mint& operator*=(const mint& other) { x *= other.x; x %= mod; return *this; } mint& operator+=(const long long n) { return *this += mint(n); } mint& operator-=(const long long n) { return *this -= mint(n); } mint& operator*=(const long long n) { return *this *= mint(n); } mint& operator=(const mint& other) { x = other.x; return *this; } mint& operator=(const long long n) { x = n % mod; return *this; } bool operator==(const mint& other) const { return x == other.x; } bool operator!=(const mint& other) const { return x != other.x; } mint operator-() const { mint res(mod - x); return res; } mint operator+(const mint& other) const { mint res(x); return res += other; } mint operator-(const mint& other) const { mint res(x); return res -= other; } mint operator*(const mint& other) const { mint res(x); return res *= other; } mint operator+(const long long n) const { mint res(x); mint other(n); return res += other; } mint operator-(const long long n) const { mint res(x); mint other(n); return res -= other; } mint operator*(const long long n) const { mint res(x); mint other(n); return res *= other; } mint pow(long long n) const { if (n == 0) return mint(1); mint res = pow(n / 2); res *= res; if (n % 2) res *= *this; return res; } mint inv() const { return pow(mod - 2); } mint& operator/=(const mint& other) { *this *= other.inv(); return *this; } mint operator/(const mint& other) const { mint res(x); return res /= other; } }; struct edge { int to, idx; }; int dfs(int v, int p, vii<edge>& to, vi<bool>& visited) { int res = -1; visited[v] = true; for (edge nv : to[v]) { if (nv.to == p) continue; if (visited[nv.to]) return nv.idx; res = max(res, dfs(nv.to, v, to, visited)); } return res; } void dfs2(int v, vii<edge>& to, vi<bool>& visited, vi<bool>& ans) { visited[v] = true; for (edge nv : to[v]) { if (visited[nv.to]) continue; if (v > nv.to) ans[nv.idx] = true; dfs2(nv.to, to, visited, ans); } } int main() { int n; cin >> n; vi<int> a(n), b(n); vii<edge> to(n); rep(i, n) { cin >> a[i] >> b[i]; a[i]--, b[i]--; to[a[i]].push_back({ b[i], i }); to[b[i]].push_back({ a[i], i }); } vi<bool> visited(n); int pos = dfs(0, -1, to, visited); rep(i, n) visited[i] = false; vi<bool> ans(n); int rt = b[pos]; dfs2(rt, to, visited, ans); rep(i, n) cout << (ans[i] ? "->" : "<-") << endl; return 0; }