Submission #27395965

Source Code Expand

(N,M),*E = $<.map{|ln| ln.split.map(&:to_i)<<$.-2 }

G = [-1]*(N+1)
F = lambda{|a|
	G[a]<0 ? a : G[a] = F[G[a]]
}
U = lambda{|a,b|
	a,b = F[a],F[b]
	next if a==b
	a,b = b,a if G[b]<G[a]
	G[a] += G[b]
	G[b] = a
	next true
}
Em,Ex = E.sort_by{_3}.partition{ U[_1,_2] }

A2B = Array.new(N+1){[]}
Ex.each{|a,b,c,e|
	A2B[a]<<[b,c,e]
	A2B[b]<<[a,c,e]
}

Sm = Em.sum{_3}
Se = [nil]*M
H = Array.new(N+1){|a|{a=>a}}
Em.each{|a,b,c,e|
	Se[e] = Sm
	a,b = b,a if H[a].sum{A2B[_2].size} < H[b].sum{A2B[_2].size}
	ha,hb,H[b] = H[a],H[b],H[a]
	hb.keys.each{|a|
		A2B[a].each{|b,cx,e|
			Se[e] ||= Sm+cx-c if ha[b]
		}
		ha[a] = a
	}
}

puts Se

Submission Info

Submission Time
Task O - Variable Spanning Trees
User ds14050
Language Ruby (2.7.1)
Score 0
Code Size 667 Byte
Status WA
Exec Time 906 ms
Memory 91092 KiB

Judge Result

Set Name All
Score / Max Score 0 / 6
Status
AC × 3
WA × 40
Set Name Test Cases
All 0.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 3.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
0.txt WA 633 ms 65404 KiB
1.txt WA 314 ms 38928 KiB
10.txt WA 629 ms 66060 KiB
11.txt WA 625 ms 66108 KiB
12.txt WA 630 ms 65900 KiB
13.txt WA 619 ms 65964 KiB
14.txt WA 614 ms 65828 KiB
15.txt WA 621 ms 65892 KiB
16.txt WA 624 ms 65812 KiB
17.txt WA 625 ms 65832 KiB
18.txt WA 640 ms 66084 KiB
19.txt WA 607 ms 65948 KiB
2.txt WA 394 ms 48388 KiB
20.txt WA 857 ms 90192 KiB
21.txt WA 864 ms 90280 KiB
22.txt WA 906 ms 91092 KiB
23.txt WA 874 ms 90104 KiB
24.txt WA 851 ms 90632 KiB
25.txt WA 838 ms 90224 KiB
26.txt WA 850 ms 90172 KiB
27.txt WA 842 ms 90684 KiB
28.txt WA 843 ms 90076 KiB
29.txt WA 840 ms 90344 KiB
3.txt WA 854 ms 80996 KiB
30.txt WA 431 ms 51084 KiB
31.txt WA 433 ms 50860 KiB
32.txt WA 429 ms 50656 KiB
33.txt WA 432 ms 50448 KiB
34.txt WA 420 ms 50616 KiB
35.txt WA 429 ms 50472 KiB
36.txt WA 430 ms 50596 KiB
37.txt WA 437 ms 50848 KiB
38.txt WA 433 ms 50704 KiB
39.txt WA 429 ms 50708 KiB
4.txt WA 726 ms 73688 KiB
5.txt WA 275 ms 36636 KiB
6.txt WA 251 ms 35928 KiB
7.txt WA 739 ms 73416 KiB
8.txt WA 333 ms 44000 KiB
9.txt WA 518 ms 63632 KiB
s1.txt AC 60 ms 14152 KiB
s2.txt AC 65 ms 14060 KiB
s3.txt AC 61 ms 14280 KiB