結果

問題 No.416 旅行会社
ユーザー TawaraTawara
提出日時 2016-08-27 08:11:01
言語 PyPy2
(7.3.15)
結果
AC  
実行時間 730 ms / 4,000 ms
コード長 522 bytes
コンパイル時間 381 ms
コンパイル使用メモリ 77,056 KB
実行使用メモリ 156,060 KB
最終ジャッジ日時 2024-05-08 15:08:31
合計ジャッジ時間 9,124 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 330 ms
119,500 KB
testcase_01 AC 72 ms
75,652 KB
testcase_02 AC 72 ms
75,648 KB
testcase_03 AC 74 ms
75,776 KB
testcase_04 AC 76 ms
75,904 KB
testcase_05 AC 75 ms
75,520 KB
testcase_06 AC 76 ms
75,388 KB
testcase_07 AC 97 ms
78,720 KB
testcase_08 AC 135 ms
80,128 KB
testcase_09 AC 187 ms
84,096 KB
testcase_10 AC 348 ms
119,528 KB
testcase_11 AC 316 ms
119,844 KB
testcase_12 AC 336 ms
119,576 KB
testcase_13 AC 336 ms
119,972 KB
testcase_14 AC 717 ms
154,656 KB
testcase_15 AC 709 ms
155,684 KB
testcase_16 AC 730 ms
156,060 KB
testcase_17 AC 700 ms
155,552 KB
testcase_18 AC 718 ms
155,164 KB
testcase_19 AC 536 ms
122,968 KB
testcase_20 AC 552 ms
123,348 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