結果

問題 No.3056 Disconnected Coloring
ユーザー haihamabossu
提出日時 2025-03-14 23:00:54
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 217 ms / 2,000 ms
コード長 1,831 bytes
コンパイル時間 2,396 ms
コンパイル使用メモリ 209,064 KB
実行使用メモリ 21,496 KB
最終ジャッジ日時 2025-03-14 23:01:05
合計ジャッジ時間 8,813 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

void solve() {
  ll n, m;
  cin >> n >> m;
  vector g(n, vector<pair<ll, ll>>());
  {
    bool ok = m % 2 == 0;
    rep(i, m) {
      ll u, v;
      cin >> u >> v, u--, v--;
      g[u].emplace_back(v, i);
      g[v].emplace_back(u, i);
      if ((u == 0 && v == n - 1) || (u == n - 1 && v == 0)) {
        ok = false;
      }
    }
    if (!ok) {
      cout << "-1\n";
      return;
    }
  }
  auto bfs = [&](ll s, ll t) -> vector<bool> {
    vector<bool> visited(n, false), used(m, false);
    deque<ll> que;
    visited[s] = true;
    que.push_back(s);
    while (!que.empty()) {
      ll u = que.front();
      que.pop_front();
      for (const auto &[v, mi] : g[u]) {
        used[mi] = true;
        if (visited[v]) {
          continue;
        }
        visited[v] = true;
        if (v == t) {
          continue;
        }
        que.push_back(v);
      }
    }
    return used;
  };
  vector<ll> use_count(m, 0);
  {
    auto used = bfs(0, n - 1);
    rep(mi, m) use_count[mi] += used[mi];
  }
  {
    auto used = bfs(n - 1, 0);
    rep(mi, m) use_count[mi] += used[mi];
  }
  vector<ll> color(m, -1);
  ll x = 0;
  for (auto s : {0ll, n - 1}) {
    for (const auto &[v, mi] : g[s]) {
      if (use_count[mi] == 2) {
        color[mi] = s > 0;
        if (color[mi] == 0)
          x--;
        else
          x++;
      }
    }
  }
  rep(mi, m) if (color[mi] == -1) {
    if (x < 0) {
      x++;
      color[mi] = 1;
    } else {
      x--;
      color[mi] = 0;
    }
  }
  rep(mi, m) cout << (color[mi] == 0 ? "B" : "R");
  cout << '\n';
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  int T = 1;
  for (int t = 0; t < T; t++) {
    solve();
  }
  return 0;
}
0