結果

問題 No.3056 Disconnected Coloring
コンテスト
ユーザー applejam
提出日時 2025-10-12 12:39:14
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,840 bytes
コンパイル時間 5,119 ms
コンパイル使用メモリ 335,408 KB
実行使用メモリ 57,184 KB
最終ジャッジ日時 2025-10-12 12:39:48
合計ジャッジ時間 30,037 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint998244353;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vmi = vector<mint>;
using vvmi = vector<vmi>;
using vvvmi = vector<vvmi>;
#define all(a) (a).begin(), (a).end()
#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define rep(i, n) rep2(i, 0, n)
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
using p = pair<int, int>;

void solve(){
    
}

int main(){

    int n, m; cin >> n >> m;
    vector<set<int>> adj(n);
    map<p, int> mp;
    rep(i, m){
        int u, v; cin >> u >> v;
        u--; v--;
        adj[u].insert(v);
        adj[v].insert(u);
        mp[{u, v}] = i;
        mp[{v, u}] = i;
    }
    if(m%2 != 0 || adj[0].count(n-1)){
        cout << -1 << endl;
        return 0;
    }
    vi col(m, -1);
    if(adj[0].size() <= m/2 && adj[n-1].size() <= m/2){
        int r = m/2;
        for(auto i : adj[0]){
            col[mp[{0, i}]] = 0;
            r--;
        }
        for(auto i : adj[n-1]){
            col[mp[{i, n-1}]] = 1;
        }
        rep(i, m){
            if(col[i] != -1)continue;
            col[i] = (r > 0 ? 0 : 1);
            r--;
        }
    }else{
        int u = (adj[0].size() > m/2 ? 0 : n-1);
        int r = 0;
        for(auto i : adj[u]){
            col[mp[{i, u}]] = (r < m/2 ? 0 : 1);
            r++;
        }
        rep(i, m){
            if(col[i] == -1)col[m] = 1;
        }
    }
    rep(i, m){
        cout << (col[i] == 1 ? "R" : "B");
    }cout << endl;
    return 0;
}
0