Submission #26353052

Source Code Expand

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]==D/2 && DsVd2[v]==D/2 }
	Eds = E[Vc].map{|v| 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

Submission Info

Submission Time
Task F - Diameter set
User ds14050
Language Ruby (2.7.1)
Score 0
Code Size 777 Byte
Status TLE
Exec Time 2208 ms
Memory 116944 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 2
AC × 28
TLE × 9
Set Name Test Cases
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
Case Name Status Exec Time Memory
even_random_00.txt AC 613 ms 88208 KiB
even_random_01.txt AC 640 ms 91184 KiB
even_random_02.txt AC 1371 ms 115120 KiB
even_random_03.txt TLE 2208 ms 116944 KiB
even_random_04.txt TLE 2208 ms 115372 KiB
even_random_05.txt AC 553 ms 71976 KiB
even_random_06.txt AC 631 ms 84096 KiB
even_random_07.txt AC 1894 ms 114724 KiB
even_random_08.txt TLE 2208 ms 111856 KiB
even_random_09.txt TLE 2208 ms 114472 KiB
even_random_10.txt AC 525 ms 58704 KiB
even_random_11.txt AC 563 ms 66100 KiB
even_random_12.txt TLE 2208 ms 116632 KiB
even_random_13.txt TLE 2208 ms 116596 KiB
even_random_14.txt TLE 2208 ms 111948 KiB
example_00.txt AC 61 ms 14088 KiB
example_01.txt AC 56 ms 14060 KiB
hand_00.txt AC 60 ms 14268 KiB
hand_01.txt TLE 2208 ms 111800 KiB
hand_02.txt AC 515 ms 48640 KiB
hand_03.txt AC 57 ms 14244 KiB
hand_04.txt AC 557 ms 40936 KiB
hand_05.txt AC 1940 ms 113660 KiB
hand_06.txt AC 526 ms 45684 KiB
hand_07.txt TLE 2208 ms 111300 KiB
odd_random_00.txt AC 490 ms 49036 KiB
odd_random_01.txt AC 511 ms 49784 KiB
odd_random_02.txt AC 543 ms 49708 KiB
odd_random_03.txt AC 529 ms 49936 KiB
odd_random_04.txt AC 551 ms 49852 KiB
odd_random_05.txt AC 563 ms 42164 KiB
random_00.txt AC 528 ms 49820 KiB
random_01.txt AC 597 ms 84052 KiB
random_02.txt AC 665 ms 86600 KiB
random_03.txt AC 510 ms 49812 KiB
random_04.txt AC 583 ms 84276 KiB
random_05.txt AC 600 ms 81368 KiB