Problem p03108 (python)

Fixed submission:

n, m = list(map(int, input().split()))

br = [list(map(int, input().split())) for _ in range(m)]

ans = []

def nc2(n):
    if n<2:
        return 0
    return n * (n-1) // 2


class UnionFind:

    def __init__(self, size):
        self.table = [-1 for _ in range(size+1)]
        self.size = [1 for _ in range(size+1)]

    def find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                    self.size[s1] += self.size[s2]
                    self.size[s2] = 0
                else:
                    self.table[s1] = s2
                    self.size[s2] += self.size[s1]
                    self.size[s1] = 0
            else:
                self.table[s1] += -1
                self.table[s2] = s1
                self.size[s1] += self.size[s2]
                self.size[s2] = 0

    def get_size(self, x):
        s1 = self.find(x)
        return self.size[s1]

    def check_same(self, x, y):
        return self.find(x) == self.find(y)

res = []
r = nc2(n)

uf = UnionFind(n)

for a, b in reversed(br):

    res.append(r)

    if not uf.check_same(a,b):
        r -= uf.get_size(a)*uf.get_size(b)

    uf.union(a,b)

for i in reversed(res):
    print(i)

Buggy submission (verdict: Runtime Error):
import math
import sys
sys.setrecursionlimit(100000)

n, m = list(map(int, input().split()))

br = [list(map(int, input().split())) for _ in range(m)]

ans = []

def nc2(n):
    if n<2:
        return 0
    return n * (n-1) // 2

subg = {i+1:i+1 for i in range(n)}

nodes = {i+1:1 for i in range(n)}

res = []
r = nc2(n)

def fetch(i):
    if i == subg[i]:
        return i
    j = fetch(subg[i])
    subg[i] = min(j, subg[i])
    return j

for a, b in reversed(br):
    # print(subg, nodes)

    if len(nodes.keys()) == 1:
        res.append(0)
        continue
    else:
        res.append(r)

    mi, ma = min(a,b), max(a,b)
    v, w = max(fetch(mi), fetch(ma)), min(fetch(mi), fetch(ma))
    
    x = nodes[v] 
    y = nodes[w]

    r += nc2(x) + nc2(y)
    r -= nc2(x+y)

    nodes[w] += nodes[v]
    del nodes[v]
    subg[mi] = w
    subg[ma] = w

for i in reversed(res):
    print(i)

Buggy submission (verdict: Runtime Error):
import math
import sys
sys.setrecursionlimit(100000)

n, m = list(map(int, input().split()))

br = [list(map(int, input().split())) for _ in range(m)]

ans = []

def ncr(n, r):
    if n<r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

subg = {i+1:i+1 for i in range(n)}

nodes = {i+1:1 for i in range(n)}

res = []
r = ncr(n, 2)

def fetch(i):
    if i == subg[i]:
        return i
    j = fetch(subg[i])
    subg[i] = min(j, subg[i])
    return j

for a, b in reversed(br):
    # print(subg, nodes)

    if len(nodes.keys()) == 1:
        res.append(0)
        continue
    else:
        res.append(r)

    mi, ma = min(a,b), max(a,b)
    v, w = max(fetch(mi), fetch(ma)), min(fetch(mi), fetch(ma))
    
    x = nodes[v] 
    y = nodes[w]

    r += ncr(x, 2) + ncr(y, 2)
    r -= ncr(x+y, 2)

    nodes[w] += nodes[v]
    del nodes[v]
    subg[mi] = w
    subg[ma] = w

for i in reversed(res):
    print(i)

Buggy submission (verdict: Runtime Error):
import math
import sys
sys.setrecursionlimit(100000)

n, m = list(map(int, input().split()))

br = [list(map(int, input().split())) for _ in range(m)]

ans = []

def ncr(n, r):
    if n<r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

subg = {i+1:i+1 for i in range(n)}

nodes = {i+1:1 for i in range(n)}

res = []
r = ncr(n, 2)

def fetch(i):
    if i == subg[i]:
        return i
    j = fetch(subg[i])
    subg[i] = j
    return j

for a, b in reversed(br):
    # print(subg, nodes)

    if len(nodes.keys()) == 1:
        res.append(0)
        continue
    else:
        res.append(r)

    mi, ma = min(a,b), max(a,b)
    v, w = max(fetch(mi), fetch(ma)), min(fetch(mi), fetch(ma))
    
    x = nodes[v] 
    y = nodes[w]

    r += ncr(x, 2) + ncr(y, 2)
    r -= ncr(x+y, 2)

    nodes[w] += nodes[v]
    del nodes[v]
    subg[mi] = w
    subg[ma] = w

for i in reversed(res):
    print(i)

Buggy submission (verdict: Runtime Error):
import math

n, m = list(map(int, input().split()))

br = [list(map(int, input().split())) for _ in range(m)]

ans = []

def ncr(n, r):
    if n<r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

subg = {i+1:i+1 for i in range(n)}

nodes = {i+1:1 for i in range(n)}

res = []
r = ncr(n, 2)

def fetch(i):
    if i == subg[i]:
        return i
    j = fetch(subg[i])
    subg[i] = j
    return j

for a, b in reversed(br):
    # print(subg, nodes)

    if len(nodes.keys()) == 1:
        res.append(0)
        continue
    else:
        res.append(r)

    mi, ma = min(a,b), max(a,b)
    v, w = max(fetch(mi), fetch(ma)), min(fetch(mi), fetch(ma))
    
    x = nodes[v] 
    y = nodes[w]

    r += ncr(x, 2) + ncr(y, 2)
    r -= ncr(x+y, 2)

    nodes[w] += nodes[v]
    del nodes[v]
    subg[mi] = w
    subg[ma] = w

for i in reversed(res):
    print(i)

Buggy submission (verdict: Runtime Error):
import math

n, m = list(map(int, input().split()))

br = [list(map(int, input().split())) for _ in range(m)]

ans = []

def ncr(n, r):
    if n<r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

subg = {i+1:i+1 for i in range(n)}

nodes = {i+1:1 for i in range(n)}

res = []
r = ncr(n, 2)

def fetch(i):
    if i == subg[i]:
        return i
    j = fetch(subg[i])
    subg[i] = j
    return j

for a, b in reversed(br):
    # print(subg, nodes)

    if len(nodes.keys()) == 1:
        res.append(0)
        continue
    else:
        res.append(r)

    mi, ma = min(a,b), max(a,b)
    
    x = nodes[fetch(mi)] 
    y = nodes[fetch(ma)]

    r += ncr(x, 2) + ncr(y, 2)
    r -= ncr(x+y, 2)

    v, w = max(fetch(mi), fetch(ma)), min(fetch(mi), fetch(ma))
    nodes[w] += nodes[v]
    del nodes[v]
    subg[mi] = w
    subg[ma] = w

for i in reversed(res):
    print(i)

Buggy submission (verdict: Runtime Error):
import math

n, m = list(map(int, input().split()))

br = [list(map(int, input().split())) for _ in range(m)]

ans = []

def ncr(n, r):
    if n<r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

subg = {i+1:i+1 for i in range(n)}

nodes = {i+1:1 for i in range(n)}

res = []
r = ncr(n, 2)

def fetch(i):
    if i == subg[i]:
        return i
    j = fetch(subg[i])
    subg[i] = j
    return j

for a, b in reversed(br):
    # print(subg, nodes)

    if len(nodes.keys()) == 1:
        res.append(0)
        continue
    else:
        res.append(r)

    mi, ma = min(a,b), max(a,b)
    
    x = nodes[fetch(mi)] 
    y = nodes[fetch(ma)]

    r += ncr(x, 2) + ncr(y, 2)
    r -= ncr(x+y, 2)
    v, w = max(fetch(mi), fetch(ma)), min(fetch(mi), fetch(ma))
    nodes[w] += nodes[v]
    del nodes[v] 
    subg[mi] = w
    subg[ma] = w

for i in reversed(res):
    print(i)

Buggy submission (verdict: Runtime Error):
import math

n, m = list(map(int, input().split()))

br = [list(map(int, input().split())) for _ in range(m)]

ans = []

def ncr(n, r):
    if n<r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

subg = {i+1:i+1 for i in range(n)}

nodes = {i+1:1 for i in range(n)}

res = []
r = ncr(n, 2)

def fetch(i):
    if i == subg[i]:
        return i
    j = fetch(subg[i])
    subg[i] = j
    return j

for a, b in reversed(br):
    # print(subg, nodes)

    if len(nodes.keys()) == 1:
        res.append(0)
        continue
    else:
        res.append(r)

    mi, ma = min(a,b), max(a,b)
    
    x = nodes[fetch(mi)] 
    y = nodes[fetch(ma)]

    r += ncr(x, 2) + ncr(y, 2)
    r -= ncr(x+y, 2)
    v, w = max(subg[a], subg[b]), min(subg[a], subg[b])
    nodes[w] += nodes[v]
    del nodes[v] 
    subg[ma] = subg[mi]

for i in reversed(res):
    print(i)