Submission #403298

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
403298	2021-05-13T02:46:13 Z	SirCovidThe19th	timeismoney (balkan11_timeismoney)	PyPy 3	45 / 100	2000 ms	29536 KB

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, n):
		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

45.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	87 ms	20164 KB	Execution failed because the return code was nonzero
2	Correct	66 ms	19448 KB	Output is correct
3	Correct	95 ms	19736 KB	Output is correct
4	Correct	120 ms	22640 KB	Output is correct
5	Correct	306 ms	27344 KB	Output is correct
6	Correct	391 ms	27764 KB	Output is correct
7	Correct	671 ms	28808 KB	Output is correct
8	Correct	1336 ms	29536 KB	Output is correct
9	Correct	73 ms	20128 KB	Output is correct
10	Correct	91 ms	21036 KB	Output is correct
11	Incorrect	98 ms	21240 KB	Output isn't correct
12	Incorrect	290 ms	27116 KB	Output isn't correct
13	Incorrect	293 ms	26660 KB	Output isn't correct
14	Incorrect	419 ms	27000 KB	Output isn't correct
15	Incorrect	519 ms	27136 KB	Output isn't correct
16	Incorrect	1977 ms	27992 KB	Output isn't correct
17	Incorrect	1778 ms	27848 KB	Output isn't correct
18	Incorrect	1949 ms	28148 KB	Output isn't correct
19	Execution timed out	2102 ms	28836 KB	Time limit exceeded
20	Execution timed out	2094 ms	28336 KB	Time limit exceeded