Problem p03684 (python)

Fixed submission:

class uf_tree():

    def __init__(self,n):
        self.n = n
        self.par = [i for i in range(n)]
        self.rank = [0 for i in range(n)]

    def indep(self):
        dep =0
        for i in range(self.n):
            if i == self.par[i]:
                dep += 1

        return dep

    def unite(self,x,y):
        if self.root(x) == self.root(y):
            return
        else:
            rootx = self.root(x)
            rooty = self.root(y)
            if self.rank[rootx] < self.rank[rooty]:
                self.par[rootx] = rooty
            else:
                self.par[rooty] = rootx
                if self.rank[rootx] == self.rank[rooty]:
                    self.rank[rootx] += 1
    def root(self,i):
        if self.par[i] == i:
            return i
        else:
            self.par[i] = self.root(self.par[i])
            return self.par[i]

    def same(self,x,y):
        return self.root(x) == self.root(y)

def kruscal(n,edge_arr):
    edge_arr.sort(key=lambda x:x[2])
    ans = []
    tree = uf_tree(n)
    for e in edge_arr:
        s = e[0]-1
        g = e[1]-1
        if tree.same(s,g):
            continue
        else:
            ans.append(e)
            tree.unite(s,g)
    return ans

p = []
edge = []
n = int(input())
for i in range(n):
    x,y = map(int,input().split())
    p.append([x,y,i+1])

p.sort(key = lambda x:x[0])
for i in range(n-1):
    cost = min(abs(p[i+1][0]-p[i][0]),abs(p[i+1][1]-p[i][1]))
    edge.append([p[i][2],p[i+1][2],cost])

p.sort(key = lambda x:x[1])
for i in range(n-1):
    cost = min(abs(p[i+1][0]-p[i][0]),abs(p[i+1][1]-p[i][1]))
    edge.append([p[i][2],p[i+1][2],cost])

ans = kruscal(n,edge)
tot = 0
for e in ans:
    tot += e[2]
print(tot)

Buggy submission (verdict: Runtime Error):



class uf_tree():

    def __init__(self,n):
        self.n = n
        self.par = [i for i in range(n)]

    def indep(self):
        dep =0
        for i in range(self.n):
            if i == self.par[i]:
                dep += 1

        return dep

    def unite(self,child,mas):
        if self.root(child) == self.root(mas):
            return
        else:
            self.par[self.root(child)] = self.root(mas)

    def root(self,i):
        if self.par[i] == i:
            return i
        else:
            self.par[i] = self.root(self.par[i])
            return self.par[i]

    def same(self,x,y):
        if self.root(x) == self.root(y):
            return True
        else:
            return False
def kruscal(n,edge_arr):
    edge_arr.sort(key=lambda x:x[2])
    ans = []
    tree = uf_tree(n)
    for e in edge_arr:
        s = e[0]-1
        g = e[1]-1
        if tree.same(s,g):
            continue
        else:
            ans.append(e)
            tree.unite(s,g)
    return ans

def main():
    n = int(input())
    p = []
    edge = []
    for i in range(n):
        x,y = map(int,input().split())
        p.append([x,y,i+1])

    p.sort(key = lambda x:x[0])
    for i in range(n-1):
        cost = min(abs(p[i+1][0]-p[i][0]),abs(p[i+1][1]-p[i][1]))
        edge.append([p[i][2],p[i+1][2],cost])

    p.sort(key = lambda x:x[1])
    for i in range(n-1):
        cost = min(abs(p[i+1][0]-p[i][0]),abs(p[i+1][1]-p[i][1]))
        edge.append([p[i][2],p[i+1][2],cost])

    ans = kruscal(n,edge)
    tot = 0
    for e in ans:
        tot += e[2]
    print(tot)

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):



class uf_tree():

    def __init__(self,n):
        self.n = n
        self.par = [i for i in range(n)]

    def indep(self):
        dep =0
        for i in range(self.n):
            if i == self.par[i]:
                dep += 1

        return dep

    def unite(self,child,mas):
        if self.root(child) == self.root(mas):
            return
        else:
            self.par[self.root(child)] = self.root(mas)

    def root(self,i):
        if self.par[i] == i:
            return i
        else:
            self.par[i] = self.root(self.par[i])
            return self.par[i]

    def same(self,x,y):
        if self.root(x) == self.root(y):
            return True
        else:
            return False
def kruscal(n,edge_arr):
    edge_arr.sort(key=lambda x:x[2])
    ans = []
    tree = uf_tree(n)
    for e in edge_arr:
        s = e[0]-1
        g = e[1]-1
        if tree.same(s,g):
            continue
        else:
            ans.append(e)
            tree.unite(s,g)
    return ans

def main():
    n = int(input())
    p = [[0,0,0] for i in range(n)]
    edge = []
    for i in range(n):
        x,y = map(int,input().split())
        p[i][0] = x
        p[i][1] = y
        p[i][2] = i+1

    p.sort(key = lambda x:x[0])
    for i in range(n-1):
        cost = min(abs(p[i+1][0]-p[i][0]),abs(p[i+1][1]-p[i][1]))
        edge.append([p[i][2],p[i+1][2],cost])

    p.sort(key = lambda x:x[1])
    for i in range(n-1):
        cost = min(abs(p[i+1][0]-p[i][0]),abs(p[i+1][1]-p[i][1]))
        edge.append([p[i][2],p[i+1][2],cost])

    ans = kruscal(n,edge)
    tot = 0
    for e in ans:
        tot += e[2]
    print(tot)

if __name__ == '__main__':
    main()