oj.uz

답안 #403298

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
403298 2021-05-13T02:46:13 Z SirCovidThe19th 시간이 돈 (balkan11_timeismoney) PyPy 3
45 / 100
 2000 ms 29536 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, 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

# 결과 실행 시간 메모리 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