結果
問題 | No.3056 Disconnected Coloring |
ユーザー |
|
提出日時 | 2025-03-14 22:58:16 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 150 ms / 2,000 ms |
コード長 | 2,136 bytes |
コンパイル時間 | 7,113 ms |
コンパイル使用メモリ | 333,560 KB |
実行使用メモリ | 17,076 KB |
最終ジャッジ日時 | 2025-03-14 22:58:31 |
合計ジャッジ時間 | 12,245 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; typedef long long ll; const int INF = 1<<30; const ll INFLL = 1LL<<60; const ll MOD = 998244353; const double INFD = 1.0E18; const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, -1, 0, 1}; //const int dx[8] = {1, 1, 0, -1, -1, -1, 0, 1}; //const int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1}; //const int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2}; //const int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1}; using Pair = pair<ll, ll>; using Graph = vector<vector<pair<int, int>>>; using mint = atcoder::modint998244353; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); int n, m; cin >> n >> m; Graph G(n); bool ok = true; for (int i = 0; i < m; i++){ int u, v; cin >> u >> v; u--; v--; if (u == 0 && v == n - 1) ok = false; G[u].push_back({v, i}); G[v].push_back({u, i}); } if (m % 2 == 1 || ok == false){ cout << -1 << endl; return 0; } atcoder::dsu uf(n); vector<char> ans(m, 'B'); int x = 0; if (G[0].size() > m / 2) x = n - 1; queue<int> q; for (auto [v, idx] : G[x]){ ans[idx] = 'R'; q.push(v); uf.merge(x, v); } int rem = m / 2 - G[x].size(); while (!q.empty()){ if (rem == 0) break; int v = q.front(); q.pop(); for (auto [nv, idx] : G[v]){ if (nv == n - 1 - x) continue; if (ans[idx] == 'R') continue; uf.merge(v, nv); ans[idx] = 'R'; rem--; if (rem == 0) break; q.push(nv); } } queue<int> q2; q2.push(n - 1 - x); while (!q2.empty()){ if (rem == 0) break; int v = q2.front(); q2.pop(); for (auto [nv, idx] : G[v]){ if (uf.same(nv, x)) continue; if (ans[idx] == 'R') continue; ans[idx] = 'R'; rem--; if (rem == 0) break; q2.push(nv); } } for (int i = 0; i < m; i++) cout << ans[i]; cout << endl; return 0; }