Submission #27932262

Source Code Expand

$ln = $<.map{|ln| ln.split.map(&:to_i) }
N,M,K = $ln.shift
UV = $ln.shift M
S = 0,*$ln.shift
Q, = $ln.shift
AB = $ln.shift Q

ST2UV = Hash.new{|h,st| h[st] = [] }
G = [-1]*(N+1)
F = lambda{|g,u|
	g[u]<0 ? u : g[u] = F[g,g[u]]
}
U = lambda{|g,u,v|
	u,v = F[g,u],F[g,v]
	next if u==v
	u,v = v,u if g[v]<g[u]
	g[u] += g[v]
	g[v] = u
}
UV.each{|u,v|
	s,t = S[u],S[v]
	if s==t
		U[G,u,v]
	else
		ST2UV[s+t+[s,t].max*K]<<[u,v]
	end
}

Ans = [nil]*Q
Q.times.group_by{|q|
	AB[q].map{|a| S[a] }.then{|st| st.sum+st.max*K }
}.each{|st,qs|
	g2 = Hash.new(-1)
	ST2UV[st].each{|u,v|
		U[g2,F[G,u],F[G,v]]
	}
	qs.each{|q|
		a,b = AB[q].map{|a| F[g2,F[G,a]] }
		Ans[q] = a==b ? 1 : 0
	}
}

puts Ans

Submission Info

Submission Time
Task E - 交易計画 (Trade Plan)
User ds14050
Language Ruby (2.7.1)
Score 100
Code Size 727 Byte
Status AC
Exec Time 2581 ms
Memory 210264 KiB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 0 / 0 5 / 5 11 / 11 42 / 42 42 / 42
Status
AC × 4
AC × 28
AC × 24
AC × 51
AC × 74
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
Subtask1 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt
Subtask2 01-01.txt, 01-04.txt, 01-05.txt, 01-11.txt, 01-12.txt, 01-15.txt, 01-19.txt, 01-23.txt, 01-24.txt, 03-01.txt, 03-04.txt, 03-05.txt, 03-11.txt, 03-15.txt, 03-19.txt, 03-23.txt, 04-01.txt, 04-04.txt, 04-05.txt, 04-11.txt, 04-15.txt, 04-19.txt, 04-23.txt, sample-03.txt
Subtask3 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 03-07.txt, 03-08.txt, 03-09.txt, 03-10.txt, 03-11.txt, 03-12.txt, 03-13.txt, 03-14.txt, 03-15.txt, 03-16.txt, 03-17.txt, 03-18.txt, 03-19.txt, 03-20.txt, 03-21.txt, 03-22.txt, 03-23.txt
Subtask4 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 03-07.txt, 03-08.txt, 03-09.txt, 03-10.txt, 03-11.txt, 03-12.txt, 03-13.txt, 03-14.txt, 03-15.txt, 03-16.txt, 03-17.txt, 03-18.txt, 03-19.txt, 03-20.txt, 03-21.txt, 03-22.txt, 03-23.txt, 04-01.txt, 04-02.txt, 04-03.txt, 04-04.txt, 04-05.txt, 04-06.txt, 04-07.txt, 04-08.txt, 04-09.txt, 04-10.txt, 04-11.txt, 04-12.txt, 04-13.txt, 04-14.txt, 04-15.txt, 04-16.txt, 04-17.txt, 04-18.txt, 04-19.txt, 04-20.txt, 04-21.txt, 04-22.txt, 04-23.txt
Case Name Status Exec Time Memory
01-01.txt AC 63 ms 14472 KiB
01-02.txt AC 63 ms 14392 KiB
01-03.txt AC 64 ms 14536 KiB
01-04.txt AC 61 ms 14104 KiB
01-05.txt AC 66 ms 14376 KiB
01-06.txt AC 62 ms 14220 KiB
01-07.txt AC 60 ms 14192 KiB
01-08.txt AC 64 ms 14176 KiB
01-09.txt AC 61 ms 14456 KiB
01-10.txt AC 66 ms 14332 KiB
01-11.txt AC 65 ms 14240 KiB
01-12.txt AC 63 ms 14496 KiB
01-13.txt AC 62 ms 14148 KiB
01-14.txt AC 64 ms 14304 KiB
01-15.txt AC 60 ms 14188 KiB
01-16.txt AC 62 ms 14276 KiB
01-17.txt AC 61 ms 14224 KiB
01-18.txt AC 64 ms 14396 KiB
01-19.txt AC 60 ms 14228 KiB
01-20.txt AC 63 ms 14084 KiB
01-21.txt AC 66 ms 14288 KiB
01-22.txt AC 62 ms 14348 KiB
01-23.txt AC 60 ms 14176 KiB
01-24.txt AC 60 ms 14360 KiB
03-01.txt AC 410 ms 42960 KiB
03-02.txt AC 420 ms 43584 KiB
03-03.txt AC 429 ms 45376 KiB
03-04.txt AC 373 ms 36356 KiB
03-05.txt AC 424 ms 43068 KiB
03-06.txt AC 379 ms 37288 KiB
03-07.txt AC 406 ms 39012 KiB
03-08.txt AC 419 ms 39120 KiB
03-09.txt AC 422 ms 41968 KiB
03-10.txt AC 434 ms 42128 KiB
03-11.txt AC 350 ms 28888 KiB
03-12.txt AC 433 ms 54980 KiB
03-13.txt AC 341 ms 38688 KiB
03-14.txt AC 397 ms 51912 KiB
03-15.txt AC 289 ms 27236 KiB
03-16.txt AC 326 ms 32768 KiB
03-17.txt AC 410 ms 45012 KiB
03-18.txt AC 384 ms 51976 KiB
03-19.txt AC 288 ms 26984 KiB
03-20.txt AC 350 ms 31616 KiB
03-21.txt AC 388 ms 38000 KiB
03-22.txt AC 413 ms 39660 KiB
03-23.txt AC 172 ms 24104 KiB
04-01.txt AC 2435 ms 152548 KiB
04-02.txt AC 2261 ms 170408 KiB
04-03.txt AC 2581 ms 180248 KiB
04-04.txt AC 2234 ms 135460 KiB
04-05.txt AC 2310 ms 169520 KiB
04-06.txt AC 2191 ms 135208 KiB
04-07.txt AC 2091 ms 134568 KiB
04-08.txt AC 2334 ms 143736 KiB
04-09.txt AC 2240 ms 160212 KiB
04-10.txt AC 2357 ms 156540 KiB
04-11.txt AC 1741 ms 92692 KiB
04-12.txt AC 2543 ms 210264 KiB
04-13.txt AC 1802 ms 138112 KiB
04-14.txt AC 2442 ms 203196 KiB
04-15.txt AC 1162 ms 60572 KiB
04-16.txt AC 1702 ms 107476 KiB
04-17.txt AC 2339 ms 169828 KiB
04-18.txt AC 1797 ms 171820 KiB
04-19.txt AC 1429 ms 82964 KiB
04-20.txt AC 1783 ms 106452 KiB
04-21.txt AC 1979 ms 136196 KiB
04-22.txt AC 2374 ms 136448 KiB
04-23.txt AC 669 ms 65684 KiB
sample-01.txt AC 57 ms 14144 KiB
sample-02.txt AC 57 ms 14060 KiB
sample-03.txt AC 57 ms 14248 KiB
sample-04.txt AC 59 ms 14152 KiB