結果

問題 No.3056 Disconnected Coloring
コンテスト
ユーザー rin204
提出日時 2024-10-20 22:48:11
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 676 ms / 2,000 ms
コード長 1,703 bytes
コンパイル時間 460 ms
コンパイル使用メモリ 82,952 KB
実行使用メモリ 165,368 KB
最終ジャッジ日時 2025-03-14 19:59:32
合計ジャッジ時間 17,703 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

n, m = map(int, input().split())
edges = [[] for _ in range(n)]
deg = [0] * n
direct = False
E = []
for _ in range(m):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    E.append((u, v))
    edges[u].append(v)
    edges[v].append(u)
    deg[u] += 1
    deg[v] += 1
    if u == 0 and v == n - 1:
        direct = True

if m % 2 == 1 or direct:
    print(-1)
    exit()

ans = ["."] * m
m //= 2
if deg[0] <= m and deg[-1] <= m:
    r = m
    b = m

    for i, (u, v) in enumerate(E):
        if u == 0:
            ans[i] = "R"
            r -= 1
        elif v == n - 1:
            ans[i] = "B"
            b -= 1

    for i in range(2 * m):
        if ans[i] != ".":
            continue
        if r > 0:
            ans[i] = "R"
            r -= 1
        else:
            ans[i] = "B"

else:
    if deg[0] > m:
        edges = [[] for _ in range(n)]
        for i, (u, v) in enumerate(E):
            u, v = n - 1 - v, n - 1 - u
            E[i] = (u, v)
            edges[u].append(v)
            edges[v].append(u)

    used = [False] * n
    used[0] = True
    used[-1] = True

    st = [0]
    while st:
        u = st.pop()
        for v in edges[u]:
            if used[v]:
                continue
            used[v] = True
            st.append(v)

    r = m
    b = m
    for i, (u, v) in enumerate(E):
        if u == 0:
            ans[i] = "R"
            r -= 1
        elif v == n - 1 and used[u]:
            ans[i] = "B"
            b -= 1

    for i in range(2 * m):
        if ans[i] != ".":
            continue
        if r > 0:
            ans[i] = "R"
            r -= 1
        else:
            ans[i] = "B"


print(*ans, sep="")
0