提出 #19823594

ソースコード 拡げる

N,M = gets.split.map(&:to_i)
E = Array.new(N+1){ [] }
M.times{
	a,b = gets.split.map(&:to_i)
	E[a] << b
	E[b] << a
}
K = gets.to_i
C = gets.split.map(&:to_i)

D = Hash.new{|h,k|
	a = [1.0/0]*(N+1)
	a[k] = d = 0
	q,r,at = [k],[]
	until q.empty?
		d += 1
		r.concat E[at].select{|to|
			a[to] = d if d < a[to]
		} while at = q.pop
		q,r = r,q
	end
	h[k] = a
}
ZAB = Array.new(1<<K){ [nil]*K }
(1<<K).times{|z|
	dz = ZAB[z]
	０,１ = K.times.partition{|k| z[k]<1 }
	０.each{|a|
		a2 = D[C[a]]
		ZAB[z|1<<a][a] = １.map{|b| a2[C[b]]+dz[b] }.min||1
	}	
}

dmin = ZAB[-1].min
p(dmin.finite? ? dmin : -1)

提出情報

提出日時
問題 E - Magical Ornament
ユーザ ds14050
言語 Ruby (2.7.1)
得点 0
コード長 636 Byte
結果 TLE
実行時間 2032 ms
メモリ 125352 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 500
結果
AC × 3
AC × 39
TLE × 1
セット名 テストケース
Sample 01_sample.txt, 02_sample.txt, 03_sample.txt
All 01_sample.txt, 02_sample.txt, 03_sample.txt, 04_hand.txt, 05_hand.txt, 06_small.txt, 07_small.txt, 08_small.txt, 09_small.txt, 10_small.txt, 11_small.txt, 12_small.txt, 13_small.txt, 14_small.txt, 15_small.txt, 16_small.txt, 17_small.txt, 18_small.txt, 19_small.txt, 20_small.txt, 21_large.txt, 22_large.txt, 23_large.txt, 24_large.txt, 25_large.txt, 26_max.txt, 27_max.txt, 28_max.txt, 29_max.txt, 30_max.txt, 31_max.txt, 32_tree.txt, 33_tree.txt, 34_tree.txt, 35_path.txt, 36_path.txt, 37_path.txt, 38_star.txt, 39_star.txt, 40_star.txt
ケース名 結果 実行時間 メモリ
01_sample.txt AC 58 ms 14248 KiB
02_sample.txt AC 58 ms 14264 KiB
03_sample.txt AC 57 ms 14280 KiB
04_hand.txt AC 59 ms 14388 KiB
05_hand.txt AC 71 ms 19792 KiB
06_small.txt AC 63 ms 14400 KiB
07_small.txt AC 58 ms 14224 KiB
08_small.txt AC 58 ms 14296 KiB
09_small.txt AC 59 ms 14276 KiB
10_small.txt AC 57 ms 14316 KiB
11_small.txt AC 60 ms 14328 KiB
12_small.txt AC 59 ms 14440 KiB
13_small.txt AC 57 ms 14376 KiB
14_small.txt AC 56 ms 14428 KiB
15_small.txt AC 58 ms 14124 KiB
16_small.txt AC 58 ms 14328 KiB
17_small.txt AC 59 ms 14384 KiB
18_small.txt AC 57 ms 14168 KiB
19_small.txt AC 57 ms 14212 KiB
20_small.txt AC 59 ms 14296 KiB
21_large.txt TLE 2032 ms 125352 KiB
22_large.txt AC 1238 ms 51772 KiB
23_large.txt AC 291 ms 24028 KiB
24_large.txt AC 346 ms 25472 KiB
25_large.txt AC 335 ms 25684 KiB
26_max.txt AC 1764 ms 76548 KiB
27_max.txt AC 1779 ms 76592 KiB
28_max.txt AC 1760 ms 76136 KiB
29_max.txt AC 1721 ms 74832 KiB
30_max.txt AC 1574 ms 69748 KiB
31_max.txt AC 1366 ms 55484 KiB
32_tree.txt AC 1767 ms 76716 KiB
33_tree.txt AC 1763 ms 76656 KiB
34_tree.txt AC 1780 ms 76932 KiB
35_path.txt AC 1776 ms 75300 KiB
36_path.txt AC 1764 ms 75056 KiB
37_path.txt AC 1759 ms 75384 KiB
38_star.txt AC 1627 ms 77624 KiB
39_star.txt AC 1672 ms 77216 KiB
40_star.txt AC 1691 ms 77352 KiB