結果

問題 No.3056 Disconnected Coloring
ユーザー navel_tos
提出日時 2025-03-21 22:37:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 673 ms / 2,000 ms
コード長 2,512 bytes
コンパイル時間 671 ms
コンパイル使用メモリ 82,904 KB
実行使用メモリ 156,288 KB
最終ジャッジ日時 2025-03-21 22:38:10
合計ジャッジ時間 18,183 ms
ジャッジサーバーID
（参考情報） 		judge7 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

#yukicoder3056 Disconnected Coloring

#入力受取
N, M = map(int, input().split())
edges = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(M)]

#正当性チェック
def check(N, M, edges, S):
    if len(S) != M:
        return False
    if any(Si not in 'RB' for Si in S):
        return False
    if not sum(Si == 'R' for Si in S) == sum(Si == 'B' for Si in S) == M // 2:
        return False
    G = [ [[] for _ in range(N)] for _ in range(2) ]
    for Si, (Ui, Vi) in zip(S, edges):
        G[Si == 'R'][Ui].append(Vi)
        G[Si == 'R'][Vi].append(Ui)
    visited = [[0] * N for _ in range(2)]
    Q, R = [], [(0, i) for i in range(2)]
    while R:
        Q, R = R, Q
        while Q:
            now, f = Q.pop()
            visited[f][now] = 1
            for nxt in G[f][now]:
                if visited[f][nxt] == 0:
                    visited[f][nxt] = 1
                    R.append((nxt, f))
    return visited[0][-1] == visited[1][-1] == 0


#愚直解
def brute(N, M, edges):
    def combination(N, K):
        yield ( S := ~ (- 1 << K) )
        if K == 0: return
        while (S := (d := S + (LSB := S & - S)) | (S & ~ d) >> LSB.bit_length()) < 1 << N:
            yield S
    for B in combination(M, M >> 1):
        S = ''.join(['R' if B >> i & 1 else 'B' for i in range(M)])
        if check(N, M, edges, S):
            return S
    return ''


def solve(N, M, edges):
    if M & 1 == 1: return ''
    if any((Ui, Vi) == (0, N - 1) or (Ui, Vi) == (N - 1, 0) for Ui, Vi in edges):
        return ''

    G = [[] for _ in range(N)]
    for i, (Ui, Vi) in enumerate(edges):
        G[Ui].append((Vi, i))
        G[Vi].append((Ui, i))
    ans = [-1] * M

    #0 ←→ N - 1の移動をしたとき、最後に入る辺はcriticalな辺なので色を確定させてよい
    for Si, Ti, Ci in [(0, N - 1, 0), (N - 1, 0, 1)]:
        visited = [0] * N
        for now in ( Q := [Si] ):
            visited[now] = 1
            for nxt, i in G[now]:
                if nxt == Ti:
                    ans[i] = Ci
                elif visited[nxt] == 0:
                    visited[nxt] = 1
                    Q.append(nxt)
    assert sum(Ai == 0 for Ai in ans) <= M // 2 >= sum(Ai == 1 for Ai in ans)
    cnt = sum(Ai == 0 for Ai in ans)
    for i in range(M):
        if ans[i] == -1:
            if cnt < M // 2: ans[i] = 0; cnt += 1
            else: ans[i] = 1
    return ''.join(['BR'[Ai] for Ai in ans])


print(ans if ( ans := solve(N, M, edges) ) != '' else -1)
0