提出 #26352819

ソースコード 拡げる

N = gets.to_i
P = 998244353
E = Array.new(N+1){[]}
$<.each{|ln|
	u,v = ln.split.map(&:to_i)
	E[u]<<v
	E[v]<<u
}

Ds = lambda{|s,p=s|
	ds = [-1]+[nil]*N
	ds[p],ds[s] = -1,0
	*q = s
	while u = q.pop
		d = ds[u]+1
		E[u].each{|v|
			next if ds[v]
			ds[v] = d
			q << v
		}
	end
	next ds
}
Ds1 = Ds[1]
Vd1 = (1..N).max_by{|v| Ds1[v] }
DsVd1 = Ds[Vd1]
Vd2 = (1..N).max_by{|v| DsVd1[v] }
DsVd2 = Ds[Vd2]
D = DsVd1[Vd2]

if D&1<1
	Vc = (1..N).find{|v| DsVd1[v]+DsVd2[v]==D }
	Eds = E[Vc].filter_map{|v;n| n if 0<n = Ds[v,Vc].count(D/2-1) }
	p (Eds.inject(1){|a,n| a*(n+1)%P }-1-Eds.sum)%P
else
	Vc1,Vc2 = (1..N).find_all{|v|
		DsVd1[v]+DsVd2[v]==D && ([DsVd1[v],DsVd2[v]]&[D/2,(D+1)/2]).size==2
	}
	p Ds[Vc1,Vc2].count(D/2)*Ds[Vc2,Vc1].count(D/2)%P
end

提出情報

提出日時
問題 F - Diameter set
ユーザ ds14050
言語 Ruby (2.7.1)
得点 0
コード長 787 Byte
結果 WA
実行時間 570 ms
メモリ 84516 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 0 / 500
結果
AC × 2
AC × 14
WA × 23
セット名 テストケース
Sample example_00.txt, example_01.txt
All even_random_00.txt, even_random_01.txt, even_random_02.txt, even_random_03.txt, even_random_04.txt, even_random_05.txt, even_random_06.txt, even_random_07.txt, even_random_08.txt, even_random_09.txt, even_random_10.txt, even_random_11.txt, even_random_12.txt, even_random_13.txt, even_random_14.txt, example_00.txt, example_01.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, odd_random_00.txt, odd_random_01.txt, odd_random_02.txt, odd_random_03.txt, odd_random_04.txt, odd_random_05.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt
ケース名 結果 実行時間 メモリ
even_random_00.txt WA 516 ms 45400 KiB
even_random_01.txt WA 506 ms 45260 KiB
even_random_02.txt WA 489 ms 45828 KiB
even_random_03.txt WA 512 ms 46708 KiB
even_random_04.txt WA 499 ms 45320 KiB
even_random_05.txt WA 546 ms 65732 KiB
even_random_06.txt WA 516 ms 46804 KiB
even_random_07.txt WA 511 ms 45328 KiB
even_random_08.txt WA 483 ms 46152 KiB
even_random_09.txt WA 505 ms 44664 KiB
even_random_10.txt WA 537 ms 49348 KiB
even_random_11.txt WA 540 ms 50616 KiB
even_random_12.txt WA 552 ms 45792 KiB
even_random_13.txt WA 514 ms 47468 KiB
even_random_14.txt WA 503 ms 45976 KiB
example_00.txt AC 56 ms 14036 KiB
example_01.txt AC 60 ms 14228 KiB
hand_00.txt AC 59 ms 14216 KiB
hand_01.txt WA 467 ms 46120 KiB
hand_02.txt AC 493 ms 48828 KiB
hand_03.txt AC 59 ms 14064 KiB
hand_04.txt AC 522 ms 41052 KiB
hand_05.txt WA 458 ms 42420 KiB
hand_06.txt WA 468 ms 42524 KiB
hand_07.txt WA 401 ms 38216 KiB
odd_random_00.txt AC 511 ms 49184 KiB
odd_random_01.txt AC 517 ms 49924 KiB
odd_random_02.txt AC 529 ms 49732 KiB
odd_random_03.txt AC 509 ms 50044 KiB
odd_random_04.txt AC 529 ms 49892 KiB
odd_random_05.txt AC 543 ms 42064 KiB
random_00.txt AC 511 ms 49944 KiB
random_01.txt WA 556 ms 71756 KiB
random_02.txt WA 538 ms 65596 KiB
random_03.txt AC 508 ms 49924 KiB
random_04.txt WA 494 ms 49792 KiB
random_05.txt WA 570 ms 84516 KiB