結果

問題 No.3056 Disconnected Coloring
ユーザー ゼリトキ
提出日時 2025-03-14 22:57:40
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,980 bytes
コンパイル時間 3,561 ms
コンパイル使用メモリ 281,816 KB
実行使用メモリ 10,064 KB
最終ジャッジ日時 2025-03-14 22:57:54
合計ジャッジ時間 12,345 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 13 WA * 8 RE * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define INF 9e18;
int N,M;
int u[20009],v[200009];
vector<pair<int,int>>G[200009];
int color[200009];
int main(){
    cin>>N>>M;
    if(M%2==1){
        cout<<"-1"<<endl;
        return 0;
    }
    for(int i=1;i<=M;i++){
        cin>>u[i]>>v[i];
        G[u[i]].push_back(make_pair(v[i],i));
        G[v[i]].push_back(make_pair(u[i],i));
        if((u[i]==1 && v[i]==N) || (u[i]==N && v[i]==1)){
            cout<<-1<<endl;
            return 0;
        }
    }
    for(int i=1;i<=M;i++) color[i]=-1;
    queue<pair<int,int>>Q;
    Q.push(make_pair(1,0));
    Q.push(make_pair(N,1));
    int blue=0;
    int red=0;
    int seigen=M/2;
    while(!Q.empty()){
        int pos=Q.front().first;
        rep(i,G[pos].size()){
            if(G[pos][i].first!=1 && G[pos][i].first!=N && color[G[pos][i].second]==-1){
                if(pos==1 && blue<seigen){
                    color[G[pos][i].second]=0;
                    Q.push(make_pair(G[pos][i].first,0));
                    blue++;
                }
                else if(pos==N && red<seigen){
                    color[G[pos][i].second]=1;
                    Q.push(make_pair(G[pos][i].first,1));
                    red++;

                }
                else{
                    if((Q.front().second==0 && blue<seigen) || (Q.front().second==1 && red<seigen)){
                        color[G[pos][i].second]=Q.front().second;
                        Q.push(make_pair(G[pos][i].first,Q.front().second));
                        if(Q.front().second==0) blue++;
                        else red++;
                    }
                }
            }
        }
        Q.pop();
    }
    for(int i=1;i<=M;i++){
        if(color[i]==-1){
            cout<<-1<<endl;
            return 0;
        }
    }
    for(int i=1;i<=M;i++){
        if(color[i]==0) cout<<"B";
        else cout<<"R";
    }
}
0