結果
問題 | No.3056 Disconnected Coloring |
ユーザー |
👑 |
提出日時 | 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 |
ソースコード
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="")