oj.uz

답안 #403342

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
403342 2021-05-13T04:47:02 Z SirCovidThe19th 시간이 돈 (balkan11_timeismoney) Python 3
50 / 100
 2000 ms 6176 KB 
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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 3672 KB Output is correct
2 Correct 24 ms 3520 KB Output is correct
3 Correct 27 ms 3420 KB Output is correct
4 Correct 36 ms 3532 KB Output is correct
5 Correct 85 ms 3592 KB Output is correct
6 Correct 96 ms 3616 KB Output is correct
7 Correct 345 ms 3936 KB Output is correct
8 Correct 1379 ms 6160 KB Output is correct
9 Correct 28 ms 3404 KB Output is correct
10 Correct 31 ms 3452 KB Output is correct
11 Incorrect 33 ms 3492 KB Output isn't correct
12 Incorrect 60 ms 3500 KB Output isn't correct
13 Incorrect 58 ms 3404 KB Output isn't correct
14 Incorrect 136 ms 3560 KB Output isn't correct
15 Incorrect 148 ms 3520 KB Output isn't correct
16 Incorrect 1315 ms 3936 KB Output isn't correct
17 Incorrect 1192 ms 3936 KB Output isn't correct
18 Incorrect 1373 ms 3936 KB Output isn't correct
19 Execution timed out 2084 ms 6176 KB Time limit exceeded
20 Execution timed out 2072 ms 6096 KB Time limit exceeded