結果
問題 | No.3056 Disconnected Coloring |
ユーザー |
![]() |
提出日時 | 2025-03-14 22:45:52 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 729 ms / 2,000 ms |
コード長 | 3,141 bytes |
コンパイル時間 | 281 ms |
コンパイル使用メモリ | 82,244 KB |
実行使用メモリ | 180,352 KB |
最終ジャッジ日時 | 2025-03-14 22:46:09 |
合計ジャッジ時間 | 15,695 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 34 |
ソースコード
import sys input = sys.stdin.readline from collections import deque def calc(ANS,EDGE): USE=[0]*M E=[[] for i in range(N)] for i in range(M): if ANS[i]=="R": x,y=EDGE[i] E[x].append(y) E[y].append(x) Q=deque() Q.append(0) USE=[0]*N USE[0]=1 while Q: x=Q.popleft() for to in E[x]: if USE[to]==0: USE[to]=1 Q.append(to) if USE[N-1]==1: return False E=[[] for i in range(N)] for i in range(M): if ANS[i]=="B": x,y=EDGE[i] E[x].append(y) E[y].append(x) Q=deque() Q.append(0) USE=[0]*N USE[0]=1 while Q: x=Q.popleft() for to in E[x]: if USE[to]==0: USE[to]=1 Q.append(to) if USE[N-1]==1: return False return True N,M=map(int,input().split()) if M%2==1: print(-1) exit() EDGE=[list(map(int,input().split())) for i in range(M)] for i in range(M): EDGE[i][0]-=1 EDGE[i][1]-=1 E=[[] for i in range(N)] for i in range(M): x,y=EDGE[i] if x==0 and y==N-1: print(-1) exit() if x==N-1 and y==0: print(-1) exit() E[x].append((y,i)) E[y].append((x,i)) Q=deque() Q.append(N-1) USE=[0]*N USE[N-1]=1 while Q: x=Q.popleft() for to,ind in E[x]: if to==0: continue if USE[to]==0: USE[to]=1 Q.append(to) LIST=[] for to,ind in E[0]: if USE[to]==1: LIST.append((to,ind)) if len(LIST)<=M//2: ANS=["R"]*M NOW=0 Q=[0] USE=[0]*N USE[0]=1 for to,ind in LIST: NOW+=1 ANS[ind]="B" USE[to]=1 Q.append(to) while Q: x=Q.pop() for to,ind in E[x]: if to==N-1: continue if ANS[ind]=="R" and NOW<M//2: ANS[ind]="B" if USE[to]==0: Q.append(to) USE[to]=1 NOW+=1 if ANS.count("R")==ANS.count("B"): print("".join(ANS)) assert calc(ANS,EDGE)==True exit() Q=deque() Q.append(0) USE=[0]*N USE[0]=1 while Q: x=Q.popleft() for to,ind in E[x]: if to==N-1: continue if USE[to]==0: USE[to]=1 Q.append(to) LIST=[] for to,ind in E[N-1]: if USE[to]==1: LIST.append((to,ind)) if len(LIST)<=M//2: ANS=["R"]*M NOW=0 Q=[N-1] USE=[0]*N USE[N-1]=1 for to,ind in LIST: NOW+=1 ANS[ind]="B" USE[to]=1 Q.append(to) while Q: x=Q.pop() for to,ind in E[x]: if to==0: continue if ANS[ind]=="R" and NOW<M//2: ANS[ind]="B" if USE[to]==0: Q.append(to) USE[to]=1 NOW+=1 if ANS.count("R")==ANS.count("B"): print("".join(ANS)) assert calc(ANS,EDGE)==True exit() print(-1)