結果

問題 No.3056 Disconnected Coloring
ユーザー V_Melville
提出日時 2025-03-14 22:34:21
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 4,355 bytes
コンパイル時間 376 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 91,008 KB
最終ジャッジ日時 2025-03-14 22:34:39
合計ジャッジ時間 17,190 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17 WA * 5 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
from collections import defaultdict

def main():
    sys.setrecursionlimit(1 << 25)
    N, M = map(int, stdin.readline().split())
    edges = []
    for _ in range(M):
        u, v = map(int, stdin.readline().split())
        edges.append((u, v))
    
    if M % 2 != 0:
        print(-1)
        return
    
    # Try to split edges into two groups with M/2 edges each
    # Check if any possible split satisfies the conditions
    # Here, we try a simple approach: split edges into first half and second half
    # and check connectivity for each group. If not, try other splits.
    
    # Function to check connectivity between 1 and N using BFS
    def is_connected(edge_indices, adj):
        visited = [False] * (N + 1)
        queue = [1]
        visited[1] = True
        while queue:
            u = queue.pop(0)
            if u == N:
                return True
            for v in adj[u]:
                if not visited[v]:
                    visited[v] = True
                    queue.append(v)
        return False
    
    # Try different splits
    # First attempt: split into first half red, second half blue
    red = edges[:M//2]
    blue = edges[M//2:]
    
    # Build adjacency lists for red and blue
    adj_red = defaultdict(list)
    for u, v in red:
        adj_red[u].append(v)
        adj_red[v].append(u)
    adj_blue = defaultdict(list)
    for u, v in blue:
        adj_blue[u].append(v)
        adj_blue[v].append(u)
    
    red_connected = is_connected(red, adj_red)
    blue_connected = is_connected(blue, adj_blue)
    
    if not red_connected and not blue_connected:
        res = ['R'] * len(red) + ['B'] * len(blue)
        print(''.join(res))
        return
    
    # If the initial split doesn't work, try another approach: alternate colors
    # For example, alternate R and B
    color = []
    for i in range(M):
        if i % 2 == 0:
            color.append('R')
        else:
            color.append('B')
    
    # Build adjacency lists for red and blue
    adj_red = defaultdict(list)
    adj_blue = defaultdict(list)
    for i in range(M):
        u, v = edges[i]
        if color[i] == 'R':
            adj_red[u].append(v)
            adj_red[v].append(u)
        else:
            adj_blue[u].append(v)
            adj_blue[v].append(u)
    
    red_connected = is_connected(edges, adj_red)
    blue_connected = is_connected(edges, adj_blue)
    
    if not red_connected and not blue_connected:
        print(''.join(color))
        return
    
    # If still not found, try another split: separate edges into two groups based on some criteria
    # For example, edges connected to 1 in red, others in blue, but need to balance counts
    # This part is heuristic and might not work for all cases, but given time constraints, proceed with this
    
    red_edges = []
    blue_edges = []
    red_count = 0
    blue_count = 0
    # Prioritize edges not connecting 1 and N
    for i in range(M):
        u, v = edges[i]
        # If the edge is part of a simple path, try to split
        if (u == 1 or v == 1) and red_count < M//2:
            red_edges.append(i)
            red_count += 1
        else:
            blue_edges.append(i)
            blue_count += 1
    # Balance the counts
    # Move from blue to red if needed
    while red_count < M//2 and blue_edges:
        idx = blue_edges.pop()
        red_edges.append(idx)
        red_count += 1
        blue_count -= 1
    # If still not balanced, move back
    while blue_count < M//2 and red_edges:
        idx = red_edges.pop()
        blue_edges.append(idx)
        blue_count += 1
        red_count -=1
    
    # Now build color string
    color = ['B'] * M
    for i in red_edges:
        color[i] = 'R'
    # Check
    adj_red = defaultdict(list)
    adj_blue = defaultdict(list)
    for i in range(M):
        u, v = edges[i]
        if color[i] == 'R':
            adj_red[u].append(v)
            adj_red[v].append(u)
        else:
            adj_blue[u].append(v)
            adj_blue[v].append(u)
    red_connected = is_connected(edges, adj_red)
    blue_connected = is_connected(edges, adj_blue)
    if not red_connected and not blue_connected:
        print(''.join(color))
        return
    
    # If all attempts fail, output -1
    print(-1)

if __name__ == "__main__":
    main()
0