Submission #69091151

Source Code Expand

puts gets.to_i.times.map{
	n = gets.to_i
	ps = gets.split.map(&:to_i)
	cs = Array.new(n+1){[]}
	ds = [1]*(n+1) # 自身を含む子孫のサイズ
	n.downto(2){|c|
		p = ps.pop
		cs[p]<<c
		ds[p] += ds[c]
	}
	最大で何回の操作を行えますか？ = lambda{|v|
		next 0 if cs[v].empty?
		黒白 = cs[v].map{|c|
			s = 最大で何回の操作を行えますか？[c]
			next s,ds[c]-s-s
		}
		黒,白 = 黒白.transpose.map(&:sum)
		wt = 黒白.map{|k,w|
			bk,wt = 黒-k,白-w
			next 0 if w<=wt
			w -= wt
			next w&1 if w/2<=bk
			w -= 2*bk
			next w
		}.max
		(ds[v]-1-wt)/2
	}
	最大で何回の操作を行えますか？[1]
}

Submission Info

Submission Time
Task D - Non-Ancestor Matching
User ds14050
Language Ruby (ruby 3.2.2)
Score 600
Code Size 670 Byte
Status AC
Exec Time 1192 ms
Memory 764588 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 1
AC × 87
Set Name Test Cases
Sample 00_sample_00.txt
All 00_sample_00.txt, 01_small_00.txt, 01_small_01.txt, 01_small_02.txt, 02_handmade_00.txt, 02_handmade_01.txt, 02_handmade_02.txt, 02_handmade_03.txt, 02_handmade_04.txt, 02_handmade_05.txt, 02_handmade_06.txt, 02_handmade_07.txt, 02_handmade_08.txt, 02_handmade_09.txt, 02_handmade_10.txt, 02_handmade_11.txt, 02_handmade_12.txt, 02_handmade_13.txt, 02_handmade_14.txt, 02_handmade_15.txt, 02_handmade_16.txt, 02_handmade_17.txt, 02_handmade_18.txt, 02_handmade_19.txt, 02_handmade_20.txt, 02_handmade_21.txt, 02_handmade_22.txt, 02_handmade_23.txt, 02_handmade_24.txt, 02_handmade_25.txt, 02_handmade_26.txt, 02_handmade_27.txt, 02_handmade_28.txt, 02_handmade_29.txt, 02_handmade_30.txt, 02_handmade_31.txt, 02_handmade_32.txt, 02_handmade_33.txt, 02_handmade_34.txt, 02_handmade_35.txt, 02_handmade_36.txt, 02_handmade_37.txt, 02_handmade_38.txt, 02_handmade_39.txt, 02_handmade_40.txt, 02_handmade_41.txt, 02_handmade_42.txt, 02_handmade_43.txt, 02_handmade_44.txt, 02_handmade_45.txt, 03_random_00.txt, 03_random_01.txt, 03_random_02.txt, 03_random_03.txt, 03_random_04.txt, 03_random_05.txt, 03_random_06.txt, 03_random_07.txt, 03_random_08.txt, 03_random_09.txt, 03_random_10.txt, 03_random_11.txt, 03_random_12.txt, 03_random_13.txt, 03_random_14.txt, 03_random_15.txt, 03_random_16.txt, 03_random_17.txt, 03_random_18.txt, 03_random_19.txt, 03_random_20.txt, 03_random_21.txt, 03_random_22.txt, 03_random_23.txt, 03_random_24.txt, 03_random_25.txt, 03_random_26.txt, 04_from_path_subtree_01.txt, 04_from_path_subtree_02.txt, 04_from_path_subtree_03.txt, 04_from_path_subtree_04.txt, 04_from_path_subtree_05.txt, 04_from_path_subtree_06.txt, 04_from_path_subtree_07.txt, 04_from_path_subtree_08.txt, 04_from_path_subtree_09.txt, 04_from_path_subtree_10.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 138 ms 17004 KiB
01_small_00.txt AC 393 ms 17980 KiB
01_small_01.txt AC 462 ms 17880 KiB
01_small_02.txt AC 451 ms 17916 KiB
02_handmade_00.txt AC 307 ms 112804 KiB
02_handmade_01.txt AC 1103 ms 762636 KiB
02_handmade_02.txt AC 672 ms 446280 KiB
02_handmade_03.txt AC 675 ms 445992 KiB
02_handmade_04.txt AC 427 ms 102516 KiB
02_handmade_05.txt AC 425 ms 102400 KiB
02_handmade_06.txt AC 713 ms 312756 KiB
02_handmade_07.txt AC 629 ms 90500 KiB
02_handmade_08.txt AC 645 ms 90456 KiB
02_handmade_09.txt AC 625 ms 90700 KiB
02_handmade_10.txt AC 381 ms 18112 KiB
02_handmade_11.txt AC 379 ms 18092 KiB
02_handmade_12.txt AC 385 ms 18112 KiB
02_handmade_13.txt AC 383 ms 18312 KiB
02_handmade_14.txt AC 378 ms 18028 KiB
02_handmade_15.txt AC 380 ms 18280 KiB
02_handmade_16.txt AC 383 ms 18352 KiB
02_handmade_17.txt AC 381 ms 18364 KiB
02_handmade_18.txt AC 574 ms 90904 KiB
02_handmade_19.txt AC 416 ms 18864 KiB
02_handmade_20.txt AC 420 ms 18896 KiB
02_handmade_21.txt AC 416 ms 18760 KiB
02_handmade_22.txt AC 419 ms 18860 KiB
02_handmade_23.txt AC 507 ms 19272 KiB
02_handmade_24.txt AC 503 ms 19520 KiB
02_handmade_25.txt AC 510 ms 19180 KiB
02_handmade_26.txt AC 505 ms 19648 KiB
02_handmade_27.txt AC 468 ms 18688 KiB
02_handmade_28.txt AC 462 ms 18600 KiB
02_handmade_29.txt AC 458 ms 18728 KiB
02_handmade_30.txt AC 463 ms 18696 KiB
02_handmade_31.txt AC 815 ms 400392 KiB
02_handmade_32.txt AC 970 ms 449328 KiB
02_handmade_33.txt AC 1089 ms 762584 KiB
02_handmade_34.txt AC 1078 ms 762564 KiB
02_handmade_35.txt AC 1115 ms 764588 KiB
02_handmade_36.txt AC 1083 ms 762536 KiB
02_handmade_37.txt AC 1078 ms 762564 KiB
02_handmade_38.txt AC 1086 ms 761492 KiB
02_handmade_39.txt AC 1098 ms 762024 KiB
02_handmade_40.txt AC 1087 ms 757768 KiB
02_handmade_41.txt AC 1018 ms 695868 KiB
02_handmade_42.txt AC 939 ms 628624 KiB
02_handmade_43.txt AC 1192 ms 546340 KiB
02_handmade_44.txt AC 1166 ms 484008 KiB
02_handmade_45.txt AC 256 ms 54872 KiB
03_random_00.txt AC 616 ms 88660 KiB
03_random_01.txt AC 635 ms 88664 KiB
03_random_02.txt AC 614 ms 87756 KiB
03_random_03.txt AC 643 ms 88748 KiB
03_random_04.txt AC 642 ms 88832 KiB
03_random_05.txt AC 677 ms 88748 KiB
03_random_06.txt AC 599 ms 88596 KiB
03_random_07.txt AC 617 ms 88548 KiB
03_random_08.txt AC 662 ms 88700 KiB
03_random_09.txt AC 647 ms 88676 KiB
03_random_10.txt AC 297 ms 113408 KiB
03_random_11.txt AC 333 ms 116324 KiB
03_random_12.txt AC 407 ms 114972 KiB
03_random_13.txt AC 415 ms 115148 KiB
03_random_14.txt AC 381 ms 18092 KiB
03_random_15.txt AC 383 ms 18212 KiB
03_random_16.txt AC 380 ms 18108 KiB
03_random_17.txt AC 383 ms 18216 KiB
03_random_18.txt AC 380 ms 18288 KiB
03_random_19.txt AC 689 ms 157680 KiB
03_random_20.txt AC 668 ms 152416 KiB
03_random_21.txt AC 697 ms 154936 KiB
03_random_22.txt AC 842 ms 261588 KiB
03_random_23.txt AC 786 ms 260104 KiB
03_random_24.txt AC 834 ms 259796 KiB
03_random_25.txt AC 733 ms 260024 KiB
03_random_26.txt AC 918 ms 262280 KiB
04_from_path_subtree_01.txt AC 1118 ms 454904 KiB
04_from_path_subtree_02.txt AC 1093 ms 575940 KiB
04_from_path_subtree_03.txt AC 1011 ms 648164 KiB
04_from_path_subtree_04.txt AC 1120 ms 505036 KiB
04_from_path_subtree_05.txt AC 959 ms 615676 KiB
04_from_path_subtree_06.txt AC 1056 ms 714784 KiB
04_from_path_subtree_07.txt AC 1064 ms 567464 KiB
04_from_path_subtree_08.txt AC 1136 ms 629264 KiB
04_from_path_subtree_09.txt AC 1133 ms 474048 KiB
04_from_path_subtree_10.txt AC 1036 ms 718728 KiB