結果

問題 No.3056 Disconnected Coloring
コンテスト
ユーザー detteiuu
提出日時 2025-10-26 22:25:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 564 ms / 2,000 ms
コード長 1,263 bytes
コンパイル時間 335 ms
コンパイル使用メモリ 82,712 KB
実行使用メモリ 141,428 KB
最終ジャッジ日時 2025-10-26 22:25:32
合計ジャッジ時間 13,890 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque

N, M = map(int, input().split())
G = [[] for _ in range(N)]
flag = False
for i in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    if (u, v) == (0, N-1):
        flag = True
    G[u].append((v, i))
    G[v].append((u, i))

if M%2 == 1:
    exit(print(-1))
if flag:
    exit(print(-1))

visited = [False]*N
visited[0] = True
que = deque()
que.append(0)
ST = set()
while que:
    n = que.popleft()
    for v, idx in G[n]:
        if visited[v]:
            continue
        if v != N-1:
            visited[v] = True
            que.append(v)
        else:
            ST.add(idx)
visited = [False]*N
visited[N-1] = True
que = deque()
que.append(N-1)
SS = set()
while que:
    n = que.popleft()
    for v, idx in G[n]:
        if visited[v]:
            continue
        if v != 0:
            visited[v] = True
            que.append(v)
        else:
            SS.add(idx)

red, blue = M//2, M//2
ans = [-1]*M
for n in SS:
    ans[n] = 0
    red -= 1
for n in ST:
    ans[n] = 1
    blue -= 1
for i in range(M):
    if ans[i] != -1:
        continue
    if red:
        ans[i] = 0
        red -= 1
    else:
        ans[i] = 1
        blue -= 1

print("".join(["R" if ans[i] == 0 else "B" for i in range(M)]))
0