結果

問題 No.3056 Disconnected Coloring
ユーザー yimiya（いみや）
提出日時 2025-03-14 22:37:33
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,490 bytes
コンパイル時間 4,459 ms
コンパイル使用メモリ 293,096 KB
実行使用メモリ 15,580 KB
最終ジャッジ日時 2025-03-14 22:37:48
合計ジャッジ時間 12,904 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
#include <iomanip>
#pragma GCC target ("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define rep(i,n) for (ll i = 0;i < (ll)(n);i++)
#define Yes cout << "Yes" << "\n"// YESの短縮
#define No cout << "No" << "\n"// NOの短縮
#define rtr0 return(0)//return(0)の短縮
#define gyakugen(x) modpow(x,mod - 2,mod);
#define agyakugen(x) modpow(x,amod - 2,amod);
using namespace std;
using ll = long long;//63bit型整数型
using ld = long double;//doubleよりも長い値を保存できるもの
using ull = unsigned long long;//符号がない64bit型整数
ll mod = 998244353;
ll amod = 1000000007;
ll MINF = -5000000000000000000;
ll INF = 5000000000000000000;
ll BAD = -1;
vector<ll>tate = {0,-1,0,1};//グリッド上の全探索時の四方向の上下のチェック
vector<ll>yoko = {1,0,-1,0};//グリッド上の全探索時の四方向の右左のチェック
vector<ll>eightx = {0,-1,-1,-1,0,1,1,1};//グリッド上の全探索時の八方向の上下のチェック
vector<ll>eighty = {1,1,0,-1,-1,-1,0,1};//グリッド上の全探索時の八方向の右左のチェック
vector<ll>hexsax = {0,1,1,0,-1,-1};
vector<ll>hexsay = {1,1,0,-1,-1,0};
//返り値は素数のリスト。

void nextbit(vector<ll>&bit,ll N,ll x){//bitと配列の長さN,x進数
	bit[0]++;
	for(ll i = 0;i<N;i++){
		if(bit[i]==x){
			bit[i]=0;
			bit[i+1]++;
		}
	}
}

vector < bool > isprime;
vector < ll > Era(int n){//書き方 vector<ll>[] = Era(x); とやるとxまでの素数が出てくる。
	isprime.resize(n, true);
	vector < ll > res;
	isprime[0] = false;
	isprime[1] = false;
	for(ll i = 2; i < n; ++i) isprime[i] = true;
	for(ll i = 2; i < n; ++i) {
		if(isprime[i]) {
			res.push_back(i);
			for(ll j = i * 2; j < n; j += i) isprime[j] = false;
		}
	}
	return res;
}
//　　　　　　素数判定 21~35

long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
//     モッドを使った累乗

template<class T>
struct dijkstra{
  public:
	vector<vector<pair<T,T>>>graph;
	vector<T>ans;
	priority_queue<pair<T,T>,vector<pair<T,T>>,greater<pair<T,T>>>pq;
	void do_dijkstra(T start){//頂点xからダイクストラを行う
		pq.push({0,start});
		ans[start] = 0;
		while(true){
			if(pq.empty())break;
			T cost = pq.top().first;
			T vertex = pq.top().second;
			pq.pop();
			for(T i = 0;i<graph[vertex].size();i++){
				T nextvertex = graph[vertex][i].first;
				T nextcost = graph[vertex][i].second + cost;
				if(ans[nextvertex] > nextcost){
					ans[nextvertex] = nextcost;
					pq.push({nextcost,nextvertex});
				}
			}
		}
	}
	void make_indirectedgraph(T u,T v,T cost){//無向辺のグラフ作成
		graph[u].push_back({v,cost});
		graph[v].push_back({u,cost});
	}
	void make_directedgraph(T u,T v,T cost){//有向辺のグラフ作成
		graph[u].push_back({v,cost});
	}
	T output(T end){//答えを出す
		return ans[end];
	} 
	void reset(T N){//リセット
		graph.clear();
		ans.clear();
		for(ll i = 0;i<N;i++){
			graph.push_back({vector<pair<T,T>>(0)});
			ans.push_back(INF);
		}
	}
};

template<class T>
struct unionfind{//主に、マージ、確認、親が同じかどうかの判定、親の確認
  public:
	vector<T>parent;
	vector<set<T>>child;
	void check(T N){//親の確認、バグ取りに有効
		for(T i = 0;i<N;i++)cout << parent[i] << " ";
		cout << "\n";
	}
	T leader(T x){//親はだれか
		return parent[x];
	}
	void marge(T x,T y){//ufのマージ
		T a = leader(x);
		T b = leader(y);
		if(a != b){
			if(child[a].size() > child[b].size()){
				while(true){
					if(child[b].empty())break;
					child[a].insert(*child[b].begin());
					parent[*child[b].begin()] = a;
					child[b].erase(*child[b].begin());
				}	
			}
			else{
				while(true){
					if(child[a].empty())break;
					child[b].insert(*child[a].begin());
					parent[*child[a].begin()] = b;
					child[a].erase(*child[a].begin());
				}	
			}
		}
	}
	bool same(T x,T y){//親が同じかどうかの判定
		T a = leader(x);
		T b = leader(y);
		if(a == b)return true;
		else return false;
	}
	void reset(T N){//始めるときの初期化
		parent.clear();
		child.clear();
		parent.resize(N);
		child.resize(N);
		for(T i = 0;i<N;i++){
			parent[i] = i;
			child[i].insert(i);
		}
	}
};
int main(){
ll N,M;
cin >> N >> M;
vector<vector<pair<ll,ll>>>graph(N,vector<pair<ll,ll>>(0));
for(ll i = 0;i<M;i++){
	ll a,b;
	cin >> a >> b;
	a--;
	b--;
	graph[a].push_back({b,i});
}
if(M%2 == 1){
	cout << -1 << "\n";
	rtr0;
}
vector<bool>visited(M);
vector<ll>color(M);
ll rcount = 0;
ll bcount = 0;
for(ll i = 0;i<graph[0].size();i++){
	ll x = graph[0][i].first;
	ll y = graph[0][i].second;
	if(x == N-1){
		cout << -1 << "\n";
		rtr0;
	}
	else{
		rcount++;
		color[y] = 0;
		visited[y] = true;
	}
}
if(rcount > M/2){
	cout << -1 << "\n";
	rtr0;
}
for(ll i = 0;i<graph[N-1].size();i++){
	ll x = graph[N-1][i].first;
	ll y = graph[N-1][i].second;
	if(x == 0){
		cout << -1 << "\n";
		rtr0;
	}
	else{
		bcount++;
		color[y] = 1;
		visited[y] = true;
	}
}
if(bcount > M/2){
	cout << -1 << "\n";
	rtr0;
}
for(ll i = 0;i<M;i++){
	if(visited[i]){
		if(color[i]==0)cout << "R";
		else cout << "B";
	}
	else{
		if(rcount < M/2){
			cout << "R";
			rcount++;
		}
		else{
			cout << "B";
			bcount++;
		}
	}
}
cout << "\n";
}
0