제출 #1166108

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166108		u6714508	시간이 돈 (balkan11_timeismoney)	Pypy 3	45 / 100	178 ms	53152 KiB

timeismoney

class unionf:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        
    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u, v):
         rootu = self.find(u)
         rootv = self.find(v)
         if rootu != rootv:
             if self.rank[rootu] > self.rank[rootv]:
                 self.parent[rootv] = rootu
             elif self.rank[rootu] < self.rank[rootv]:
                 self.parent[rootu] = rootv
             else:
                 self.parent[rootv] = rootu
                 self.rank[rootu] += 1

def kruskal(n ,map1):
    map1.sort(key=lambda x: (x[2], x[3]))
    uf  = unionf(n)
    mst = []
    sumt , sumc = 0 , 0
    for u , v , t ,c in map1:
        if uf.find(u) != uf.find(v):
            uf.union(u,v)
            mst.append((u, v))
            sumt += t
            sumc += c
        if len(mst) == n-1:
              break
    return sumt , sumc , mst

N, M = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]
#N = 5 
#M = 7 
#edges = [
#    (0, 1, 161, 79),
#    (0, 2, 161, 15),
#   (0, 3, 13, 153),
#    (1, 4, 142, 183),
#    (1, 4, 236, 80),
#    (2, 4, 40, 241),
#    (2, 1, 65, 92)
#] 
sumt, sumc, mst = kruskal(N, edges)
print(sumt, sumc)
for u, v in mst:
    print(u, v)

컴파일 시 표준 출력 (stdout) 메시지

Compiling 'timeismoney.py'...

=======
  adding: __main__.pyc (deflated 45%)

=======

• Subtask 1: 45 / 100