Submission #403342

#	Time	Username	Problem	Language	Result	Execution time	Memory
403342		SirCovidThe19th	timeismoney (balkan11_timeismoney)	Cpython 3	50 / 100	2084 ms	6176 KiB

timeismoney

import math
from functools import cmp_to_key

class edg:
	def __init__(self, x, y, t, c):
		self.x = x
		self.y = y
		self.t = t
		self.c = c

class dsu:
	def __init__(self):
		global n
		self.par = []
		self.sz = []
		for i in range(n):
			self.par.append(i)
			self.sz.append(i)
	def find(self, node):
		if (self.par[node] != node):
			self.par[node] = self.find(self.par[node])
		return self.par[node]
	def merge(self, a, b):
		a, b = self.find(a), self.find(b)
		if (self.sz[a] > self.sz[b]):
			a, b = b, a
		self.par[a] = b
		self.sz[b] += self.sz[a]

n, m = 0, 0
timeLCM, moneyLCM = 0, 0
edges = []

currVal = 0
ansT, ansC, link = 0, 0, []

def getLCM():
	global edges, timeLCM, moneyLCM
	timeLCM, moneyLCM = edges[0].t, edges[0].c
	for i in range(1, m):
		timeLCM = timeLCM*edges[i].t//math.gcd(timeLCM, edges[i].t)
		moneyLCM = moneyLCM*edges[i].t//math.gcd(moneyLCM, edges[i].t)

def check(whichSort):
	global n, m, edges, currVal, timeLCM, moneyLCM, ansT, ansC, link
	if (whichSort == 1):
		edges.sort(key=cmp_to_key(lambda a, b: (a.t-(((timeLCM/a.c)*currVal)/timeLCM)) - (b.t-(((timeLCM/b.c)*currVal)/timeLCM))))
	if (whichSort == 2):
		edges.sort(key=cmp_to_key(lambda a, b: (a.c-(((moneyLCM/a.t)*currVal)/moneyLCM)) - (b.c-(((moneyLCM/b.t)*currVal)/moneyLCM))))
	
	uf = dsu()
	ansT, ansC, link = 0, 0, []

	for i in range(m):
		if (uf.find(edges[i].x) != uf.find(edges[i].y)):
			uf.merge(edges[i].x, edges[i].y)
			ansT += edges[i].t
			ansC += edges[i].c
			link.append([edges[i].x, edges[i].y])
	return ansT*ansC <= currVal

def solve():
	global n, m, edges, currVal
	n, m = map(int, input().split())
	for i in range(m):
		x, y, t, c = map(int, input().split())
		edges.append(edg(x, y, t, c))
	getLCM()

	low, high = 0, 255*n*255*n+1
	while (low < high):
		currVal = (low+high+1)//2
		if (check(1)):
			high = currVal-1
		elif (check(2)):
			high = currVal-1
		else:
			low = currVal
	
	print(ansT, ansC)
	for i in range(len(link)):
		print(link[i][0], link[i][1])
	
solve()

• Subtask 1: 50 / 100