Submission #14435898

Source Code Expand

N = gets.to_i
A = gets.split.map(&:to_i)
E = Array.new(N){ [] }
(N-1).times{
	u,v = gets.split.map(&:to_i)
	E[u-1]<<v-1
	E[v-1]<<u-1
}
B = [nil]*N
F = lambda{|u,a|
	next if B[u]
	i = a.bsearch_index{|_| A[u]<=_ }||a.size
	z,a[i] = a[i],A[u]
	B[u] = a.size
	E[u].each{|v|
		F[v,a]
	}
	if z
		a[i] = z
	else
		a.pop
	end
}
F[0,[]]
p(*B)

Submission Info

Submission Time
Task F - LIS on Tree
User ds14050
Language Ruby (2.7.1)
Score 600
Code Size 360 Byte
Status AC
Exec Time 707 ms
Memory 259260 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 1
AC × 17
Set Name Test Cases
Sample Sample_01.txt
All Sample_01.txt, caterpillar_01.txt, ni_01.txt, ni_02.txt, ni_03.txt, path_02.txt, path_04.txt, path_07.txt, path_08.txt, rand_01.txt, rand_02.txt, rand_03.txt, rand_04.txt, rand_05.txt, rand_large_01.txt, same_01.txt, star_01.txt
Case Name Status Exec Time Memory
Sample_01.txt AC 61 ms 14012 KiB
caterpillar_01.txt AC 615 ms 107220 KiB
ni_01.txt AC 61 ms 14100 KiB
ni_02.txt AC 58 ms 14256 KiB
ni_03.txt AC 67 ms 14072 KiB
path_02.txt AC 679 ms 191384 KiB
path_04.txt AC 611 ms 83144 KiB
path_07.txt AC 652 ms 125084 KiB
path_08.txt AC 669 ms 179848 KiB
rand_01.txt AC 59 ms 14172 KiB
rand_02.txt AC 65 ms 14040 KiB
rand_03.txt AC 59 ms 14116 KiB
rand_04.txt AC 66 ms 14076 KiB
rand_05.txt AC 66 ms 13928 KiB
rand_large_01.txt AC 528 ms 55188 KiB
same_01.txt AC 707 ms 259260 KiB
star_01.txt AC 465 ms 53592 KiB