結果

問題 No.3056 Disconnected Coloring
ユーザー otoshigo
提出日時 2025-03-14 21:41:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 107 ms / 2,000 ms
コード長 3,196 bytes
コンパイル時間 2,387 ms
コンパイル使用メモリ 206,448 KB
実行使用メモリ 17,336 KB
最終ジャッジ日時 2025-03-14 21:41:47
合計ジャッジ時間 7,385 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
template<class T> bool chmax(T &a, T b){if (a < b){a = b;return true;} else return false;}
template<class T> bool chmin(T &a, T b){if (a > b){a = b;return true;} else return false;}

const int INF=1<<30;

void Solve(){
    int N,M;
    cin>>N>>M;
    vector<vector<pair<int,int>>>G(N);
    bool flag=false;
    if(M%2==1)flag=true;
    for(int i=0;i<M;i++){
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        if(a>b)swap(a,b);
        if(a==0&&b==N-1){
            flag=true;
        }
        G[a].push_back({b,i});
        G[b].push_back({a,i});
    }
    if(flag){
        cout<<-1<<"\n";
        return;
    }
    auto find_dist=[&](int x,int no)-> vector<int> {
        queue<pair<int,int>>q;
        vector<int>dist(N,INF);
        q.push({0,x});
        dist[x]=0;
        while(q.size()){
            auto[c,y]=q.front();
            q.pop();
            if(y==no)continue;
            if(dist[y]<c)continue;
            for(auto[i,e]:G[y]){
                if(chmin(dist[i],c+1)){
                    q.push({dist[i],i});
                }
            }
        }
        return dist;
    };
    if((int)G[0].size()<=M/2&&(int)G[N-1].size()<=M/2){
        vector<int>isRed(M,-1);
        int sum=0;
        for(auto[i,e]:G[0]){
            isRed[e]=1;
            sum++;
        }
        for(auto[i,e]:G[N-1]){
            isRed[e]=0;
        }
        for(int i=0;i<M;i++){
            if(isRed[i]!=-1)continue;
            if(sum<M/2){
                isRed[i]=1;
                sum++;
            }else{
                isRed[i]=0;
            }
        }
        for(int i=0;i<M;i++){
            if(isRed[i])cout<<'R';
            else cout<<'B';
        }
        cout<<"\n";
    }else if((int)G[0].size()>M/2){
        vector<int>D=find_dist(N-1,0);
        vector<int>isRed(M,-1);
        int sum=0;
        for(auto[i,e]:G[0]){
            if(D[i]!=INF){
                isRed[e]=1;
                sum++;
            }
        }
        for(auto[i,e]:G[N-1]){
            isRed[e]=0;
        }
        for(int i=0;i<M;i++){
            if(isRed[i]!=-1)continue;
            if(sum<M/2){
                isRed[i]=1;
                sum++;
            }else{
                isRed[i]=0;
            }
        }
        for(int i=0;i<M;i++){
            if(isRed[i])cout<<'R';
            else cout<<'B';
        }
        cout<<"\n";
    }else{
        vector<int>D=find_dist(0,N-1);
        vector<int>isRed(M,-1);
        int sum=0;
        for(auto[i,e]:G[0]){
            isRed[e]=1;
            sum++;
        }
        for(auto[i,e]:G[N-1]){
            if(D[i]!=INF)isRed[e]=0;
        }
        for(int i=0;i<M;i++){
            if(isRed[i]!=-1)continue;
            if(sum<M/2){
                isRed[i]=1;
                sum++;
            }else{
                isRed[i]=0;
            }
        }
        for(int i=0;i<M;i++){
            if(isRed[i])cout<<'R';
            else cout<<'B';
        }
        cout<<"\n";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Solve();
}
0