結果

問題 No.3056 Disconnected Coloring
ユーザー tnakao0123
提出日時 2025-03-18 13:07:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 187 ms / 2,000 ms
コード長 1,787 bytes
コンパイル時間 886 ms
コンパイル使用メモリ 65,552 KB
実行使用メモリ 31,584 KB
最終ジャッジ日時 2025-03-18 13:07:43
合計ジャッジ時間 6,381 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:38:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   38 |   scanf("%d%d", &n, &m);
      |   ~~~~~^~~~~~~~~~~~~~~~
main.cpp:43:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   43 |     scanf("%d%d", &u, &v);
      |     ~~~~~^~~~~~~~~~~~~~~~

ソースコード

diff # 

/* -*- coding: utf-8 -*-
 *
 * 3056.cc:  No.3056 Disconnected Coloring - yukicoder
 */

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<utility>

using namespace std;

/* constant */

const int MAX_N = 200000;
const int MAX_M = 200000;
const char ecs[] = "BR";
enum { B, R };

/* typedef */

using qi = queue<int>;
using pii = pair<int,int>;
using vpii = vector<pii>;

/* global variables */

vpii nbrs[MAX_N], rnbrs[MAX_N];
int ds[MAX_N], es[MAX_M];

/* subroutines */

/* main */

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  if (m & 1) { puts("-1"); return 0; }
  
  for (int i = 0; i < m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    u--, v--;
    if (u == 0 && v == n - 1) { puts("-1"); return 0; }
    nbrs[u].push_back({v, i});
    nbrs[v].push_back({u, i});
  }

  fill(ds, ds + n, -1);
  ds[0] = 0;
  qi q;
  q.push(0);

  while (! q.empty()) {
    int u = q.front(); q.pop();
    if (u == n - 1) continue;

    for (auto [v, ei]: nbrs[u]) {
      rnbrs[v].push_back({u, ei});
      if (ds[v] < 0) {
	ds[v] = ds[u] + 1;
	q.push(v);
      }
    }
  }

  fill(es, es + m, -1);
  fill(ds, ds + n, -1);
  ds[n - 1] = 0;
  q.push(n - 1);
  int cb = 0, cr = 0;

  while (! q.empty()) {
    int u = q.front(); q.pop();
    if (u == 0) continue;
    
    for (auto [v, ei]: rnbrs[u]) {
      if (u == n - 1) es[ei] = R, cr++;
      if (v == 0) es[ei] = B, cb++;
      if (ds[v] < 0) {
	ds[v] = ds[u] + 1;
	q.push(v);
      }
    }
  }

  int hm = m / 2;
  for (int i = 0; i < m; i++)
    if (es[i] < 0) {
      if (cb < hm) es[i] = B, cb++;
      else if (cr < hm) es[i] = R, cr++;
    }
  //for (int i = 0; i < m; i++) printf(" %d", es[i]); putchar('\n');
  
  for (int i = 0; i < m; i++) putchar(ecs[es[i]]); putchar('\n');

  return 0;
}
0