結果

問題 No.3056 Disconnected Coloring
ユーザー ardririy
提出日時 2025-03-14 22:09:10
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 4,529 bytes
コンパイル時間 2,811 ms
コンパイル使用メモリ 213,888 KB
実行使用メモリ 21,248 KB
最終ジャッジ日時 2025-03-14 22:09:21
合計ジャッジ時間 8,855 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 25 WA * 9
権限があれば一括ダウンロードができます

ソースコード

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};


/// @brief Union-Find 木
/// @note 1.4 高速化 + 省メモリ化
/// @see https://zenn.dev/reputeless/books/standard-cpp-for-competitive-programming/viewer/union-find
class UnionFind
{
public:

	UnionFind() = default;

	/// @brief Union-Find 木を構築します。
	/// @param n 要素数
	explicit UnionFind(size_t n)
		: m_parentsOrSize(n, -1) {}

	/// @brief 頂点 i の root のインデックスを返します。
	/// @param i 調べる頂点のインデックス
	/// @return 頂点 i の root のインデックス
	int find(int i)
	{
		if (m_parentsOrSize[i] < 0)
		{
			return i;
		}

		// 経路圧縮
		return (m_parentsOrSize[i] = find(m_parentsOrSize[i]));
	}

	/// @brief a のグループと b のグループを統合します。
	/// @param a 一方のインデックス
	/// @param b 他方のインデックス
	void merge(int a, int b)
	{
		a = find(a);
		b = find(b);

		if (a != b)
		{
			// union by size (小さいほうが子になる）
			if (-m_parentsOrSize[a] < -m_parentsOrSize[b])
			{
				std::swap(a, b);
			}

			m_parentsOrSize[a] += m_parentsOrSize[b];
			m_parentsOrSize[b] = a;
		}
	}

	/// @brief a と b が同じグループに属すかを返します。
	/// @param a 一方のインデックス
	/// @param b 他方のインデックス
	/// @return a と b が同じグループに属す場合 true, それ以外の場合は false
	bool connected(int a, int b)
	{
		return (find(a) == find(b));
	}

	/// @brief i が属するグループの要素数を返します。
	/// @param i インデックス
	/// @return i が属するグループの要素数
	int size(int i)
	{
		return -m_parentsOrSize[find(i)];
	}

private:

	// m_parentsOrSize[i] は i の 親,
	// ただし root の場合は (-1 * そのグループに属する要素数)
	std::vector<int> m_parentsOrSize;
};

void solve() {
    int n, m; cin >> n >> m;
    if(m%2==1) {
        cout << "-1\n";
        return;
    }

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

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

    if(!uf.connected(0, n-1)) {
        string ans = "";
        rep(i, m) ans += (i%2==0) ? 'B' : 'R';
        cout << ans << "\n";
        return;
    }

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

    vector<char> ans(m, '@');
    ll cnt_b = 0;
    ll cnt_r = 0;
    rep(i, m) {
        auto [u, v] = e[i];
        if(u==0 || v==0) {
            cnt_b += 1;
            ans[i] = 'B';
        } else if(u == n-1 || v == n-1) {
            cnt_r += 1;
            ans[i] = 'R';
        } 
    }
    if(cnt_b>m/2 || cnt_r>m/2) {
        cout << "-1\n";
        return;
    } else {
        rep(i, m) {
            if(ans[i] == '@') {
                if(cnt_b < m/2) {
                    ans[i] ='B';
                    cnt_b += 1;
                }
                else ans[i] = 'R';
            }
        }
        rep(i, m) {
            cout << ans[i];
        }
        cout << '\n';
    }
}

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