結果

問題 No.416 旅行会社
ユーザー TawaraTawara
提出日時 2016-08-27 08:11:01
言語 PyPy2
(7.3.15)
結果
AC  
実行時間 770 ms / 4,000 ms
コード長 522 bytes
コンパイル時間 2,166 ms
コンパイル使用メモリ 76,800 KB
実行使用メモリ 156,060 KB
最終ジャッジ日時 2024-12-14 20:02:41
合計ジャッジ時間 10,780 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 387 ms
119,440 KB
testcase_01 AC 85 ms
75,648 KB
testcase_02 AC 86 ms
75,648 KB
testcase_03 AC 85 ms
75,264 KB
testcase_04 AC 85 ms
75,520 KB
testcase_05 AC 86 ms
75,392 KB
testcase_06 AC 89 ms
75,904 KB
testcase_07 AC 112 ms
78,720 KB
testcase_08 AC 146 ms
80,128 KB
testcase_09 AC 203 ms
84,096 KB
testcase_10 AC 385 ms
119,244 KB
testcase_11 AC 364 ms
119,928 KB
testcase_12 AC 377 ms
119,548 KB
testcase_13 AC 363 ms
119,928 KB
testcase_14 AC 757 ms
154,904 KB
testcase_15 AC 770 ms
156,060 KB
testcase_16 AC 741 ms
155,732 KB
testcase_17 AC 743 ms
155,680 KB
testcase_18 AC 728 ms
155,288 KB
testcase_19 AC 546 ms
123,480 KB
testcase_20 AC 567 ms
123,472 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

X=xrange;I=lambda:map(int,raw_input().split())
N,M,Q=I()
O=10**6;R=[0]*N;A=[0]*N;B=set()
L=[[] for i in X(N)]
E=[I()for i in X(M+Q)]
for i in X(Q):f,t=E[M+i];B|={f+t*O};B|={f*O+t}
for i in X(M):
	f,t=E[i]
	if f+t*O not in B:L[f-1]+=[t-1];L[t-1]+=[f-1]
def dfs(h,R,A):
	q=[[O,h]]
	while q:
		b,h=q.pop()
		if R[h]^1:
			R[h]=1;A[h]=T
			for n in L[h]:
				if b^n:q+=[[h,n]]
T=-1;dfs(0,R,A)
for T in X(Q,0,-1):
	f,t=E[M+T-1];f-=1;t-=1
	L[f]+=[t];L[t]+=[f]
	if R[f]:dfs(t,R,A)
	elif R[t]:dfs(f,R,A)
for i in X(1,N):print A[i]
0