結果
問題 |
No.3056 Disconnected Coloring
|
ユーザー |
|
提出日時 | 2025-03-14 21:56:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 280 ms / 2,000 ms |
コード長 | 1,638 bytes |
コンパイル時間 | 2,435 ms |
コンパイル使用メモリ | 207,372 KB |
実行使用メモリ | 18,460 KB |
最終ジャッジ日時 | 2025-03-14 21:57:02 |
合計ジャッジ時間 | 9,812 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/dsu> using namespace std; int main() { int n, m; cin >> n >> m; if (m % 2 == 1) { cout << -1 << endl; return 0; } vector<vector<pair<int, int>>> g(n); vector<int> e(m, -1); atcoder::dsu uf1(n), uf2(n); for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; if (a == 1 && b == n) { cout << -1 << endl; return 0; } --a; --b; g[a].emplace_back(b, i); g[b].emplace_back(a, i); if (a != 0 && b != n - 1) { uf1.merge(a, b); uf2.merge(a, b); } } for (const auto& x : g[0]) { uf1.merge(g[0][0].first, x.first); } for (const auto& x : g[n - 1]) { uf2.merge(g[n - 1][0].first, x.first); } for (const auto& x : g[0]) { if (uf2.same(x.first, g[n - 1][0].first)) { e[x.second] = 0; } } for (const auto& x : g[n - 1]) { if (uf1.same(x.first, g[0][0].first)) { e[x.second] = 1; } } if (count(e.begin(), e.end(), 0) > m / 2 || count(e.begin(), e.end(), 1) > m / 2) { cout << -1 << endl; return 0; } int dif = m / 2 - count(e.begin(), e.end(), 0); for (int i = 0; i < m; i++) { if (e[i] == -1) { if (dif != 0) { dif--; e[i] = 0; } else { e[i] = 1; } } } string ans; for (int x : e) { ans += (x == 0 ? 'B' : 'R'); } cout << ans << endl; return 0; }