結果
| 問題 |
No.3056 Disconnected Coloring
|
| コンテスト | |
| ユーザー |
ゼリトキ
|
| 提出日時 | 2025-03-15 13:11:22 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 2,279 bytes |
| コンパイル時間 | 3,879 ms |
| コンパイル使用メモリ | 283,116 KB |
| 実行使用メモリ | 824,320 KB |
| 最終ジャッジ日時 | 2025-03-15 13:11:41 |
| 合計ジャッジ時間 | 19,425 ms |
|
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 32 MLE * 1 -- * 1 |
ソースコード
#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[200009],v[200009];
vector<pair<int,int>>G[200009];
bool already_point[200009];
bool already_line[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;
int blue=0,red=0;
for(int i=1;i<=N;i++) already_point[i]=false;
for(int i=1;i<=M;i++) already_line[i]=false;
queue<int>Q;
Q.push(1);
while(!Q.empty()){
int pos=Q.front();
if(pos==N){
Q.pop();
continue;
}
already_point[pos]=true;
rep(i,G[pos].size()){
if(already_point[G[pos][i].first]==false){
Q.push(G[pos][i].first);
if(G[pos][i].first==N) already_line[G[pos][i].second]=true;
}
}
Q.pop();
}
for(int i=1;i<=M;i++){
if(already_line[i]==true){
color[i]=0;
blue++;
}
}
for(int i=1;i<=N;i++) already_point[i]=false;
for(int i=1;i<=M;i++) already_line[i]=false;
Q.push(N);
while(!Q.empty()){
int pos=Q.front();
if(pos==1){
Q.pop();
continue;
}
already_point[pos]=true;
rep(i,G[pos].size()){
if(already_point[G[pos][i].first]==false){
Q.push(G[pos][i].first);
if(G[pos][i].first==1) already_line[G[pos][i].second]=true;
}
}
Q.pop();
}
for(int i=1;i<=M;i++){
if(already_line[i]==true){
color[i]=1;
red++;
}
}
for(int i=1;i<=M;i++){
if(color[i]==-1){
if(blue<M/2){
color[i]=0;
blue++;
}
else color[i]=1;
}
}
for(int i=1;i<=M;i++){
if(color[i]==0) cout<<"B";
else cout<<"R";
}
}
ゼリトキ