結果

問題 No.3056 Disconnected Coloring
ユーザー ardririy
提出日時 2025-03-14 23:10:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 213 ms / 2,000 ms
コード長 3,058 bytes
コンパイル時間 2,877 ms
コンパイル使用メモリ 209,560 KB
実行使用メモリ 20,464 KB
最終ジャッジ日時 2025-03-14 23:10:41
合計ジャッジ時間 8,460 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define all(v) v.begin(),v.end()
#define resort(v) sort(v.rbegin(),v.rend())
using ll = long long;
using ull = unsigned long long;
using vll=vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll,ll>;
using vp=vector<pair<ll, ll>>;

const ll inf=1ll<<60;
#define mod10 (ll)1e9+7
#define mod99 (ll)998244353
const double PI = acos(-1);

#define rep(i,n) for (ll i=0;i<n;++i)
#define per(i,n) for(ll i=n-1;i>=0;--i)
#define rep2(i,a,n) for (ll i=a;i<n;++i)
#define per2(i,a,n) for (ll i=n-1;i>=a;--i)


template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }

ll dx[] = {1, 0, -1, 0, -1, 1, -1, 1};
ll dy[] = {0, 1, 0, -1, -1, 1, 1, -1};

void solve() {
    int n, m; cin >> n >> m;

    vp e(m);
    ll u, v;
    rep(i, m) {
        cin >> u >> v;
        u--; v--;
        e[i] = {u, v};
    }

    if(m%2==1) {
        cout << "-1\n";
        return;
    }
    vvll g(n);

    for(auto[u, v]: e) {
        if(u==0&&v==n-1) {
            cout << "-1\n";
            return;
        }
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<bool> seen(n, false);
    seen[0] = true;
    stack<ll> stk;
    stk.push(0);
    while(!stk.empty()) {
        ll p = stk.top(); stk.pop();
        if(p>=0) {
            for(ll ni: g[p]) {
                if(!seen[ni]) {
                    seen[ni] = true;
                    if(ni != n-1) {
                        stk.push(ni);
                    }
                }
            }
        }
    }

    vector<bool> itrvl(n, false);
    itrvl[n-1] = true;
    assert(stk.empty());
    stk.push(n-1);
    while(!stk.empty()) {
        ll p = stk.top(); stk.pop();
        for(ll ni: g[p]) {
            if(seen[ni] && !itrvl[ni]) {
                if(ni != 0) {
                    stk.push(ni);
                    itrvl[ni] = true;
                }
            }
        }
    }


    vector<char> ans(m, '@');
    ll cnt_b = 0;
    ll cnt_r = 0;
    rep(i, m) {
        ll u = e[i].first;
        ll v = e[i].second;
        if(u==0 && itrvl[v]) {
            cnt_b += 1;
            ans[i] = 'B';
        } else if(itrvl[u] && v == n-1) {
            cnt_r += 1;
            ans[i] = 'R';
        } 
    }

    if(cnt_b*2>m || cnt_r*2>m) {
        cout << "-1\n";
        return;
    } else {
        rep(i, m) {
            if(ans[i] == '@') {
                if(cnt_b*2 < m) {
                    ans[i] ='B';
                    cnt_b += 1;
                }
                else ans[i] = 'R';
            }
        }
        ll c1 = 0, c2 = 0;
        rep(i, m) {
            assert(ans[i] != '@');
            if(ans[i] == 'R') c1 ++;
            else c2 ++;
            cout << ans[i];
        }
        assert(c1*2 == m);
        assert(c2*2 == m);
        cout << '\n';
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t=1;
    //cin >> t;
    while(t--)solve();
}
0