結果

問題 No.3056 Disconnected Coloring
ユーザー ardririy
提出日時 2025-03-14 22:00:14
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,039 bytes
コンパイル時間 7,035 ms
コンパイル使用メモリ 228,532 KB
実行使用メモリ 22,148 KB
最終ジャッジ日時 2025-03-14 22:00:31
合計ジャッジ時間 15,186 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 14 WA * 20
権限があれば一括ダウンロードができます

ソースコード

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>n/2 && cnt_r>n/2) {
        cout << "-1\n";
        return;
    } else {
        rep(i, m) {
            if(ans[i] == '@') {
                if(cnt_b < n/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