結果

問題 No.3056 Disconnected Coloring
ユーザー ripity
提出日時 2025-03-14 21:33:13
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,575 bytes
コンパイル時間 4,852 ms
コンパイル使用メモリ 264,896 KB
実行使用メモリ 17,568 KB
最終ジャッジ日時 2025-03-14 21:33:27
合計ジャッジ時間 12,896 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
 
#include <atcoder/all>
using namespace atcoder;
 
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
 
using ll = long long;
using mint = modint998244353;

int main() {
  int N, M;
  cin >> N >> M;
  bool no = false;
  vector<vector<pair<int, int>>> G(N);
  for(int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    if(u == 1 && v == N) no = true;
    G[u - 1].push_back(make_pair(v - 1, i));
    G[v - 1].push_back(make_pair(u - 1, i));
  }
  if(M % 2 == 1 || no) {
    cout << -1 << "\n";
  }else if(G[0].size() > M / 2) {
    int r = 0, b = 0;
    string S(M, '?');
    unordered_set<int> st;
    for(const auto [v, i] : G[N - 1]) {
      st.insert(v);
      S[i] = 'R';
      r++;
    }
    for(const auto [v, i] : G[0]) {
      if(st.count(v)) {
        S[i] = 'B';
        b++;
      }
    }
    for(auto g : G) {
      for(const auto [v, i] : g) {
        if(S[i] != '?') continue;
        if(r < M / 2) S[i] = 'R', r++;
        else S[i] = 'B', b++;
      }
    }
    cout << S << endl;
  }else {
    int r = 0, b = 0;
    string S(M, '?');
    unordered_set<int> st;
    for(const auto [v, i] : G[0]) {
      st.insert(v);
      S[i] = 'R';
      r++;
    }
    for(const auto [v, i] : G[N - 1]) {
      if(st.count(v)) {
        S[i] = 'B';
        b++;
      }
    }
    for(auto g : G) {
      for(const auto [v, i] : g) {
        if(S[i] != '?') continue;
        if(r < M / 2) S[i] = 'R', r++;
        else S[i] = 'B', b++;
      }
    }
    cout << S << endl;
  }
}
0