Submission #26837318

Source Code Expand

def no!; puts'No'; exit end

N = gets.to_i
E = Array.new(N){[]}
(N-1).times{
	a,b = gets.split.map{_1.to_i-1}
	E[a] << b
	E[b] << a
}

D = E.map(&:size)
V = [nil]*N
gets.to_i.times{
	v,p = gets.split.map(&:to_i)
	V[v-1] = p,p
}
Q = N.times.select{ D[_1]<2 }
while a = Q.pop
	D[a] -= 1
	break unless p = E[a].find{ 0<D[_1] }
	Q << p if 1 == D[p] -= 1
	(l,r),(lp,rp) = V[a],V[p]
	next unless l
	l -= 1; r += 1
	if lp
		no! if 0<(l^lp)&1
		l,r = [l,lp].max,[r,rp].min
		no! if r<l
	end
	V[p] = l,r
end

V[a], = V[a]
Q << a
while a = Q.pop
	v = V[a]
	E[a].each{|b|
		l,r = V[b]
		next if l && ! r
		V[b] = [v-1,v+1].find{|v| ! (l && v<l || r && r<v) }
		Q << b
	}
end

puts'Yes',V

Submission Info

Submission Time
Task E - Integers on a Tree
User ds14050
Language Ruby (2.7.1)
Score 800
Code Size 722 Byte
Status AC
Exec Time 434 ms
Memory 32900 KiB

Judge Result

Set Name sample All
Score / Max Score 0 / 0 800 / 800
Status
AC × 3
AC × 39
Set Name Test Cases
sample sample_01.txt, sample_02.txt, sample_03.txt
All binary_01.txt, binary_02.txt, hand_01.txt, hand_02.txt, hand_03.txt, kary_01.txt, kary_02.txt, kary_03.txt, line_01.txt, line_02.txt, line_03.txt, line_04.txt, line_05.txt, line_06.txt, random0_01.txt, random1_01.txt, random1_02.txt, random1_03.txt, random1_04.txt, random1_05.txt, random1_06.txt, random1_07.txt, random1_08.txt, random2_01.txt, random2_02.txt, random2_03.txt, random2_04.txt, random2_05.txt, random2_06.txt, random3_01.txt, random3_02.txt, random4_01.txt, random4_02.txt, random4_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, star_01.txt, star_02.txt
Case Name Status Exec Time Memory
binary_01.txt AC 344 ms 27496 KiB
binary_02.txt AC 204 ms 25612 KiB
hand_01.txt AC 58 ms 14256 KiB
hand_02.txt AC 57 ms 14180 KiB
hand_03.txt AC 57 ms 14100 KiB
kary_01.txt AC 165 ms 24392 KiB
kary_02.txt AC 290 ms 30396 KiB
kary_03.txt AC 185 ms 30552 KiB
line_01.txt AC 169 ms 23936 KiB
line_02.txt AC 295 ms 26480 KiB
line_03.txt AC 299 ms 27692 KiB
line_04.txt AC 331 ms 26928 KiB
line_05.txt AC 199 ms 26920 KiB
line_06.txt AC 229 ms 27140 KiB
random0_01.txt AC 198 ms 26852 KiB
random1_01.txt AC 304 ms 26060 KiB
random1_02.txt AC 320 ms 26140 KiB
random1_03.txt AC 333 ms 26260 KiB
random1_04.txt AC 395 ms 29060 KiB
random1_05.txt AC 305 ms 26340 KiB
random1_06.txt AC 309 ms 26196 KiB
random1_07.txt AC 321 ms 25696 KiB
random1_08.txt AC 434 ms 32900 KiB
random2_01.txt AC 170 ms 26068 KiB
random2_02.txt AC 199 ms 26288 KiB
random2_03.txt AC 201 ms 26136 KiB
random2_04.txt AC 200 ms 26232 KiB
random2_05.txt AC 218 ms 29000 KiB
random2_06.txt AC 282 ms 32736 KiB
random3_01.txt AC 215 ms 26444 KiB
random3_02.txt AC 224 ms 29004 KiB
random4_01.txt AC 306 ms 26092 KiB
random4_02.txt AC 308 ms 25864 KiB
random4_03.txt AC 308 ms 26284 KiB
sample_01.txt AC 58 ms 14252 KiB
sample_02.txt AC 56 ms 14308 KiB
sample_03.txt AC 59 ms 14060 KiB
star_01.txt AC 334 ms 28652 KiB
star_02.txt AC 192 ms 26820 KiB