fork download 
  1. import os, sys, getpass
  2. import math, random, decimal, queue, heapq, bisect, itertools, functools, collections, string, operator, timeit, pprint
  3. from bisect import bisect, bisect_left
  4. from collections import defaultdict, OrderedDict, deque, Counter
  5. from functools import cmp_to_key, lru_cache, partial, partialmethod, reduce
  6. from heapq import heapify, heappush, heappushpop, heappop, heapreplace, nlargest, nsmallest
  7. from itertools import accumulate, chain, combinations, combinations_with_replacement, compress, count, cycle, dropwhile, filterfalse, groupby, islice, permutations, product, repeat, starmap, takewhile, tee, zip_longest
  8. from math import gcd, factorial, isqrt, comb, perm, prod
  9. from queue import Queue, PriorityQueue, LifoQueue
  10. from random import choice, choices, shuffle, sample, random, randint, randrange, uniform, seed, getstate, setstate, getrandbits
  11. from string import ascii_letters, ascii_lowercase, ascii_uppercase, digits, hexdigits, octdigits, punctuation, printable, whitespace
  12. from typing import List, Optional, Tuple, Dict, Set, Union, Any
  13.  
  14. sys.stdin = open(os.path.join(os.getcwd(), 'a1.txt'), 'r') if getpass.getuser() == '4a' else sys.stdin
  15. I = lambda: [int(a) for l in sys.stdin for a in l.strip().split()]
  16. S = lambda: [a for l in sys.stdin for a in l.strip().split()]
  17. IM = lambda: [[int(a) for a in l.split()] for l in sys.stdin]
  18. SM = lambda: [[a for a in l.split()] for l in sys.stdin]
  19. D = lambda k=1: {i: list(map(int, input().split())) for i in range(1, 1 + int(input()) * k)}
  20. DS = lambda: {i: [(int(x[0]), x[1]) for _ in range(int(input()))
  21.                   for x in [input().split()]] for i in range(int(input()))}
  22.  
  23. moore = ((1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1))
  24. von = ((1, 0), (0, 1), (-1, 0), (0, -1))
  25. az, AZ, mod, inf = ascii_lowercase, ascii_uppercase, 1_000_000_007, float('inf')
  26. CNR = lambda n, r: factorial(n) // (factorial(r) * factorial(n - r))
  27. PNR = lambda n, r: factorial(n) // factorial(r)
  28.  
  29. A = IM()
  30. print(A) if getpass.getuser() == '4a' else None
  31.  
  32.  
  33. def solution(A):
  34.     class Kruskal:
  35.         def __init__(self, G):
  36.             self.G = G
  37.             self.parent = {}
  38.             self.rank = {}
  39.             self.make_sets()
  40.  
  41.         def make_sets(self):
  42.             for u, v in self.G:
  43.                 if u not in self.parent:
  44.                     self.parent[u] = u
  45.                     self.rank[u] = 0
  46.                 if v not in self.parent:
  47.                     self.parent[v] = v
  48.                     self.rank[v] = 0
  49.  
  50.         def find(self, x):
  51.             if self.parent[x] != x:
  52.                 self.parent[x] = self.find(self.parent[x])
  53.             return self.parent[x]
  54.  
  55.         def union(self, u, v):
  56.             su, sv = self.find(u), self.find(v)
  57.             if su != sv:
  58.                 if self.rank[su] > self.rank[sv]:
  59.                     self.parent[sv] = su
  60.                 else:
  61.                     self.parent[su] = sv
  62.                     if self.rank[su] == self.rank[sv]:
  63.                         self.rank[sv] += 1
  64.  
  65.         def _mst(self):
  66.             mst = []
  67.             for edge in self.G.keys():
  68.                 u, v = edge
  69.                 if self.find(u) != self.find(v):
  70.                     self.union(u, v)
  71.                     mst.append((u, v, self.G[edge]))
  72.             return mst
  73.  
  74.     N, M = A[0]
  75.     graph = defaultdict(int)
  76.     for i in range(1, len(A)):
  77.         if i % 2 == 1:
  78.             k, c = A[i]
  79.         else:
  80.             edges = A[i]
  81.             for ii in range(len(edges)):
  82.                 for jj in range(ii + 1, len(edges)):
  83.                     if edges[ii] < edges[jj]:
  84.                         if (edges[jj], edges[ii]) not in graph or (edges[ii], edges[jj]) not in graph:
  85.                             graph[(edges[jj], edges[ii])] = c
  86.                             graph[(edges[ii], edges[jj])] = c
  87.                             continue
  88.                         if (edges[jj], edges[ii]) in graph and graph[(edges[jj], edges[ii])] > c:
  89.                             graph[(edges[jj], edges[ii])] = c
  90.                         if (edges[ii], edges[jj]) in graph and graph[(edges[ii], edges[jj])] > c:
  91.                             graph[(edges[ii], edges[jj])] = c
  92.  
  93.     kruskal = Kruskal(graph)
  94.     MST = kruskal._mst()
  95.     res = 0
  96.     nodes = set()
  97.     # print(MST)
  98.     for x, y, z in sorted(MST, key=lambda o: o[-1]):
  99.         res += z
  100.         nodes.update({x, y})
  101.  
  102.     if sorted(nodes) != list(range(1, N + 1)):
  103.         print(-1)
  104.     else:
  105.         print(res)
  106.  
  107.  
  108. solution(A)
  109.  
Runtime error #stdin #stdout #stderr 0.16s 27300KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
Traceback (most recent call last):
  File "./prog.py", line 14, in <module>
  File "/usr/lib/python3.9/getpass.py", line 169, in getuser
    return pwd.getpwuid(os.getuid())[0]
KeyError: 'getpwuid(): uid not found: 20034'
https://ideone.com/lLHHa2
language:
Python 3 (python  3.9.5)
created:
15 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!