Problem:


Score : 500 points

Problem Statement

There are N towns on a plane. The i-th town is located at the coordinates (x_i,y_i). There may be more than one town at the same coordinates.

You can build a road between two towns at coordinates (a,b) and (c,d) for a cost of min(|a-c|,|b-d|) yen (the currency of Japan). It is not possible to build other types of roads.

Your objective is to build roads so that it will be possible to travel between every pair of towns by traversing roads. At least how much money is necessary to achieve this?

Constraints

2 ≤ N ≤ 10^5

0 ≤ x_i,y_i ≤ 10^9

All input values are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

Print the minimum necessary amount of money in order to build roads so that it will be possible to travel between every pair of towns by traversing roads.

Sample Input 1

3
1 5
3 9
7 8

Sample Output 1

3

Build a road between Towns 1 and 2, and another between Towns 2 and 3. The total cost is 2+1=3 yen.

Sample Input 2

6
8 3
4 9
12 19
18 1
13 5
7 6

Sample Output 2

8



Sample input:
3
1 5
3 9
7 8


Sample output:
3

Submission status: Runtime Error

Solution code:

n = int(input())
a = []*n

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

e = [[None for i in range(3)]for j in range(n)]
a.sort()

for i in range(n-1):
    idx1 = a[i][2]
    idx2 = a[i+1][2]
    c = abs(a[i][0]-a[i+1][0])
    if e[idx1][2] is not None:
        if e[idx1][2] > c:
            e[idx1] = [idx1,idx2,c]
    else:
        e[idx1] = [idx1,idx2,c]
a.sort(key=lambda a:a[1])

for i in range(n-1):
    idx1 = a[i][2]
    idx2 = a[i+1][2]
    c = abs(a[i][1]-a[i+1][1])
    if e[idx1][2] is not None:
        if e[idx1][2] > c:
            e[idx1] = [idx1,idx2,c]
    else:
        e[idx1] = [idx1,idx2,c]

e.sort(key=lambda e:e[2])
l = [0]*n
ans = 0
for i in range(len(e)):
    if e[i]:
        idx1 = e[i][0]
        idx2 = e[i][1]
        c = e[i][2]
        if l[idx1] == 0 or l[idx2] == 0:
            ans += c
            l[idx1] = 1
            l[idx2] = 1


print(ans)

Submission status: Runtime Error

Solution code:

n = int(input())
a = []*n

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

e = [0]*n
a.sort()

for i in range(n-1):
    idx1 = a[i][2]
    idx2 = a[i+1][2]
    c = abs(a[i][0]-a[i+1][0])
    e[idx1] = [idx1,idx2,c]
a.sort(key=lambda a:a[1])

for i in range(n-1):
    idx1 = a[i][2]
    idx2 = a[i+1][2]
    c = abs(a[i][1]-a[i+1][1])
    if e[idx1] :
        if e[idx1][2] > c:
            e[idx1] = [idx1,idx2,c]
    else:
        e[idx1] = [idx1,idx2,c]

e.sort(key=lambda e:e[2])
l = [0]*n
ans = 0
for i in range(len(e)):
    idx1 = e[i][0]
    idx2 = e[i][1]
    c = e[i][2]
    if l[idx1] == 0 or l[idx2] == 0:
        ans += c
        l[idx1] = 1
        l[idx2] = 1

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import defaultdict
import networkx as nx


def build_road_3():
	n = int(raw_input())
	cords = []
	for i in range(n):
		cords.append([int(e) for e in raw_input().split(" ")])
	cords = np.array(cords)
	x_cord = cords[:, 0]
	y_cord = cords[:, 1]
	# print x_cord
	sorted_indecies_x = np.argsort(x_cord)
	# print sorted_indecies_x
	sorted_indecies_y = np.argsort(y_cord)
	dict_weight_edges = defaultdict(list)
	for i in range(n - 1):
		s1 = sorted_indecies_x[i]
		d1 = sorted_indecies_x[i + 1]
		dis1 = abs(x_cord[s1] - x_cord[d1])
		dict_weight_edges[dis1].append((s1, d1))
		s2 = sorted_indecies_y[i]
		d2 = sorted_indecies_y[i + 1]
		dis2 = abs(y_cord[s2] - y_cord[d2])
		dict_weight_edges[dis2].append((s2, d2))
	sorted_keys = sorted(list(dict_weight_edges.keys()))
	G = nx.DiGraph()
	ans = 0
	for k in sorted_keys:
		if len(G.edges())==n-1:
			print ans
			return
		for e in dict_weight_edges.get(k):
			G.add_edge(*e)
			if list(nx.simple_cycles(G)):
				G.remove_edge(*e)
			else:
				ans = ans+k
	return


if __name__ == "__main__":
	build_road_3()

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse import csr_matrix
from collections import defaultdict
from scipy.sparse.csgraph import minimum_spanning_tree

def build_road_2():
	n = int(raw_input())
	cords = []
	for i in range(n):
		cords.append([int(e) for e in raw_input().split(" ")])
	cords = np.array(cords)
	x_cord = cords[:, 0]
	y_cord = cords[:, 1]
	# print x_cord
	sorted_indecies_x = np.argsort(x_cord)
	# print sorted_indecies_x
	sorted_indecies_y = np.argsort(y_cord)
	mutual_distance = np.zeros((n, n), dtype=int)
	dict_edge_weight = defaultdict(list)
	for i in range(n-1):
		s1 = sorted_indecies_x[i]
		d1 = sorted_indecies_x[i+1]
		dis1 = abs(x_cord[s1]-x_cord[d1])
		dict_edge_weight[(s1, d1)].append(dis1)
		s2 = sorted_indecies_y[i]
		d2 = sorted_indecies_y[i + 1]
		dis2 = abs(y_cord[s2] - y_cord[d2])
		dict_edge_weight[(s2, d2)].append(dis2)
	for key, value in dict_edge_weight.iteritems():
		mutual_distance[key[0]][key[1]] = min(value)
	ans = minimum_spanning_tree(csr_matrix(mutual_distance))
	ans = ans.toarray().astype(int)
	print ans.sum()


if __name__ == "__main__":
	build_road_2()

Submission status: Runtime Error

Solution code:
import numpy as np
from scipy.sparse import csr_matrix

def build_road():
	n = int(raw_input())
	cords = []
	for i in range(n):
		cords.append([int(e) for e in raw_input().split(" ")])
	# print cords
	mutual_distance = np.zeros((n, n))
	# print mutual_distance
	for i in range(n):
		for j in range(n):
			mutual_distance[i][j] = \
				min(abs(cords[i][0]-cords[j][0]),
					abs(cords[i][1]-cords[j][1]))
	from scipy.sparse.csgraph import minimum_spanning_tree
	mutual_distance = csr_matrix(mutual_distance)
	ans = minimum_spanning_tree(mutual_distance)
	ans = ans.toarray().astype(int)
	print ans.sum()


if __name__ == "__main__":
	build_road()

Submission status: Runtime Error

Solution code:
from scipy.sparse.csgraph import minimum_spanning_tree
import numpy as np

def build_road():
	n = int(raw_input())
	cords = []
	for i in range(n):
		cords.append([int(e) for e in raw_input().split(" ")])
	# print cords
	mutual_distance = np.zeros((n, n))
	# print mutual_distance
	for i in range(n):
		for j in range(n):
			mutual_distance[i][j] = \
				min(abs(cords[i][0]-cords[j][0]),
					abs(cords[i][1]-cords[j][1]))
	ans = minimum_spanning_tree(mutual_distance)
	ans = ans.toarray().astype(int)
	print ans.sum()


if __name__ == "__main__":
	build_road()

Submission status: Runtime Error

Solution code:
import numpy as np

def build_road():
	n = int(raw_input())
	cords = []
	for i in range(n):
		cords.append([int(e) for e in raw_input().split(" ")])
	# print cords
	mutual_distance = np.zeros((n, n))
	# print mutual_distance
	for i in range(n):
		for j in range(n):
			mutual_distance[i][j] = \
				min(abs(cords[i][0]-cords[j][0]),
					abs(cords[i][1]-cords[j][1]))
	from scipy.sparse.csgraph import minimum_spanning_tree
	ans = minimum_spanning_tree(mutual_distance)
	ans = ans.toarray().astype(int)
	print ans.sum()


if __name__ == "__main__":
	build_road()

Submission status: Runtime Error

Solution code:
s UnionFind(object):

    def __init__(self, n):
        self.n = n
        self.par = list(range(n))
        self.rank = [1] * n

    def is_same(self, a, b):
        return self.root(a) == self.root(b)

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

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


N = int(input())
X = []
Y = []
for i in range(N):
    x, y = map(int, input().split())
    X.append((x, i))
    Y.append((y, i))

X = sorted(X)
Y = sorted(Y)
graph = []
for i in range(N - 1):
    graph.append((X[i + 1][0] - X[i][0], X[i][1], X[i + 1][1]))
    graph.append((Y[i + 1][0] - Y[i][0], Y[i][1], Y[i + 1][1]))

graph.sort()
uf = UnionFind(N)

total_cost = 0
for cost, a, b in graph:
    if not uf.is_same(a, b):
        uf.unite(a, b)
        total_cost += cost

print(total_cost)

Submission status: Runtime Error

Solution code:
length = int(input())
target = []
for i in range(length):
    a,b = (int(n) for n in input().split(" "))
    target.append([a,b,i])
target.sort()
bef_x,bef_y = -1,-1
for i in range(length-1,-1,-1):
    if bef_x == target[i][0] and bef_y == target[i][1]:
        target.pop(i)
        length -= 1
    else:
        bef_x = target[i][0]
        bef_y = target[i][1]

x_sorted = target[:]
y_sorted = (sorted(target,key=lambda x:x[1]))[:]
count = 0
already = set()
now_x = 0
now_y = 0
now_rev_x = length - 1
now_rev_y = length - 1
answer = 0
# print(x_sorted)
# print(y_sorted)
while count < length - 1:

    x_diff = abs(x_sorted[now_x][0] - x_sorted[now_x + 1][0])
    rev_x_diff = abs(x_sorted[now_rev_x][0] - x_sorted[now_rev_x - 1][0])
    y_diff = abs(y_sorted[now_y][1] - y_sorted[now_y + 1][1])
    rev_y_diff = abs(y_sorted[now_rev_y][1] - y_sorted[now_rev_y - 1][1])

    min_choice = min(x_diff,rev_x_diff,y_diff,rev_y_diff)

    if min_choice == x_diff:
        real_index = {x_sorted[now_x][2],x_sorted[now_x + 1][2]}
        if (real_index - already):
            answer += min_choice
            already |= real_index
            now_x += 1
        else:
            now_x += 1
    elif min_choice == y_diff:
        real_index = {y_sorted[now_y][2],y_sorted[now_y + 1][2]}
        if (real_index - already):
            answer +=  min_choice
            already |= real_index
            now_y += 1
        else:
            now_y += 1

    elif min_choice == rev_x_diff:
        real_index = {x_sorted[now_rev_x][2],x_sorted[now_rev_x - 1][2]}
        if ({real_index - 1} - already):
            answer += min_choice
            already |= real_index
            now_rev_x -= 1
        else:
            now_rev_x -= 1
    else:
        real_index = {y_sorted[now_rev_y][2],y_sorted[now_rev_y - 1][2]}
        if (real_index - already):
            answer +=  min_choice
            already |= real_index
            now_rev_y -= 1
        else:
            now_rev_y -= 1
    if now_x == now_rev_x:
        x_sorted[now_x] = float("inf")
    elif now_y == now_rev_y:
        y_sorted[now_y] = float("inf")
    # print(x_diff,rev_x_diff,y_diff,rev_y_diff,now_x,now_rev_x,now_y,now_rev_y,answer,already)
    count += 1
print(answer)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
int Nmax = 100;
vector <tuple <int,int,int>> xbe; // x,y,index
vector <tuple <int,int,int>> ybe; // y,x,index
int n;
int counter = 0;
int result = 0;
struct graph{
    int name = 0;
    vector <pair <int ,int>> nodes;
};
vector <graph*> nodes;
vector <graph*> con;
int use[10000];


int mst(){
    counter++;
    if(counter == n) return result;
    int x;
    int dist = 10e12;
    graph* node;
    for(int i = 0; i < con.size(); i++){
        node = con[i];
        for(int j = 0; j < node -> nodes.size(); j++ ){
            if(use[get<0>(node -> nodes[j])] != 1){
                if(dist > get<1>(node -> nodes[j])) {
                    dist = get<1>(node -> nodes[j]);
                    x = get<0>(node -> nodes[j])  ;
                }
            }
        }
    }
    use[x] = 1;
    result = result +dist;
    con.push_back(nodes[x]);
    return mst();
}




int main(void){
    cin >> n;
    for(int i = 0; i < n; i ++) use[i] = 0;
    for(int i = 0; i < n; i++){
        int x,y;
        cin >> x >> y;
        xbe.push_back(tuple<int,int,int> (x,y,i));
        ybe.push_back(tuple<int,int,int> (y,x,i));
        graph* A = new graph;
        A -> name = i;
        nodes.push_back(A);
    }
    sort(xbe.begin(), xbe.end());
    sort(ybe.begin(), ybe.end());
    for(int i = 0; i < n - 1; i++){
        int x1,y1,x2,y2,i1,i2,dis;
        tuple<int,int,int> X1 = xbe[i];
        tuple<int,int,int> X2 = xbe[i+1];
        tuple<int,int,int> Y1 = ybe[i];
        tuple<int,int,int> Y2 = ybe[i+1];
        x1 = get <0>(X1);
        y1 = get <1>(X1);
        i1 = get <2>(X1);
        x2 = get <0>(X2);
        y2 = get <1>(X2);
        i2 = get <2>(X2);
        //cout << x1 << " " << y1 << " " << x2 << " " << y2 <<  "\n";
        dis = min(abs(x2-x1),abs(y2-y1));
        //cout << dis << "\n";
        nodes[i1] -> nodes.push_back(pair <int, int>(i2,dis));
        nodes[i2] -> nodes.push_back(pair <int, int>(i1,dis));
        x1 = get <0>(Y1);
        y1 = get <1>(Y1);
        i1 = get <2>(Y1);
        x2 = get <0>(Y2);
        y2 = get <1>(Y2);
        i2 = get <2>(Y2);
        dis = min(abs(x2-x1),abs(y2-y1));
        nodes[i1] -> nodes.push_back(pair <int, int>(i2,dis));
        nodes[i2] -> nodes.push_back(pair <int, int>(i1,dis));
        //cout << x1 << " " << y1 << " " << x2 << " " << y2 <<  "\n";
        //cout << dis << "\n";
        //graph[i2][i1], graph[i1][i2] = min(x2-x1, y2-y2);
    }
    con.push_back(nodes[0]);
    use[0] = 1;
    int result = mst();
    cout << result << "\n";
    // Here your code !
    
}

Submission status: Runtime Error

Solution code:
import numpy as np

N=int(input())
pos_mat=np.zeros((N,2))
for i in range(N):
    buf=input().split()
    pos_mat[i,0]=int(buf[0])
    pos_mat[i,1]=int(buf[1])

cost_mat=np.zeros((N,N))
for u in range(N):
    for v in range(u+1, N):
        cost_mat[u,v]=min(abs(pos_mat[u, 0]-pos_mat[v,0]), abs(pos_mat[u, 1]-pos_mat[v,1]))

print(0)

#minCost_arr=np.array([float("inf") for _ in range(N)])
#used_arr=np.zeros(N, dtype=bool)
#minCost_arr[0]=0
#
#totalCost=0
#while np.sum(used_arr)<N:
#
#    idx=np.arange(N)[~used_arr]
#    u=idx[np.argmin(minCost_arr[idx])]
#
#    totalCost+=minCost_arr[u]
#    used_arr[u]=True
#    for v in range(N):
#        edgeCost=cost_mat[min(u,v), max(u,v)]
#        minCost_arr[v]=min(minCost_arr[v], edgeCost)
#print(int(totalCost))

Submission status: Runtime Error

Solution code:
import numpy as np

N=int(input())
pos_mat=np.zeros((N,2))
for i in range(N):
    buf=input().split()
    pos_mat[i,0]=int(buf[0])
    pos_mat[i,1]=int(buf[1])
    
cost_mat=np.zeros((N,N))
for u in range(N):
    for v in range(u+1, N):
        cost_mat[u,v]=min(abs(pos_mat[u, 0]-pos_mat[v,0]), abs(pos_mat[u, 1]-pos_mat[v,1]))

        
minCost_arr=np.array([float("inf") for _ in range(N)])
used_arr=np.zeros(N, dtype=bool)
minCost_arr[0]=0

totalCost=0
while np.sum(used_arr)<N:
    
    idx=np.arange(N)[~used_arr]
    u=idx[np.argmin(minCost_arr[idx])]
    
    totalCost+=minCost_arr[u]
    used_arr[u]=True
    for v in range(N):
        edgeCost=cost_mat[min(u,v), max(u,v)]
        minCost_arr[v]=min(minCost_arr[v], edgeCost)
print(int(totalCost))

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))

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

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s1] = s2
                self.table[s2] += self.table[s1]
            return True
        return False

N = ni()
a = []
b = []
for i in range(N):
    x, y = na()
    a.append((x, i))
    b.append((y, i))

a.sort()
b.sort()
t = []
for i in range(1, N):
    t.append((a[i][0]-a[i-1][0], a[i][1], a[i-1][1]))
    t.append((b[i][0]-b[i-1][0], b[i][1], b[i-1][1]))

t.sort()
ans = 0
uf = UnionFind(N)
for c, d, e in t:
    if uf.union(d,e):
        ans += c

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from heapq import *

N=int(input())
pos_mat=np.zeros((N,2))
for i in range(N):
    buf=input().split()
    pos_mat[i,0]=int(buf[0])
    pos_mat[i,1]=int(buf[1])
    
cost_mat=np.zeros((N,N))
for u in range(N):
    for v in range(u+1, N):
        cost_mat[u,v]=min(abs(pos_mat[u, 0]-pos_mat[v,0]), abs(pos_mat[u, 1]-pos_mat[v,1]))

minCost=[float("inf") for _ in range(N)]
minCost[0]=0
totalCost=0

h=[]#list of (cost, vertex ID)
heappush(h, (0, 0))
while(len(h)>0):
    cost, u=heappop(h)
    if cost>minCost[u]:
        continue
    totalCost+=cost
    for v in range(N):
        edgeCost=cost_mat[min(u,v), max(u,v)]
        if (minCost[v]>edgeCost):
            minCost[v]=edgeCost
            heappush(h,(minCost[v],v))
            
print(int(totalCost))

Submission status: Runtime Error

Solution code:
class UnionFind:
    def __init__(self, size):
        self.parents = list(range(size))

    def find(self, i):
        ret = i
        path = []
        while self.parents[ret]!=ret:
            path.append(ret)
            ret = self.parents[ret]
        for p in path:
            self.parents[p] = ret
        return ret

    def union(self, i, j):
        self.parents[self.find(i)] = j

n = int(input())
xys = [(*map(int, input().split()), i) for i in range(n)]

sortx = sorted(xys, key=lambda xy: xy[0])
roadsx = [(sortx[i][0]-sortx[i-1][0], sortx[i][2], sortx[i-1][2]) for i in range(1, n)]
sorty = sorted(xys, key=lambda xy: xy[1])
roadsy = [(sorty[i][1]-sorty[i-1][1], sorty[i][2], sorty[i-1][2]) for i in range(1, n)]
roads = roadsx + roadsy
roads.sort(key=lambda x:x[0])

ctr = 1
ans = 0
uf = UnionFind(n)
for road in roads:
    if ctr >= n:
        break
    cost, i1, i2 = road
    if uf.find(i1) != uf.find(i2):
        ans += cost
        ctr += 1
        uf.union(i1, i2)

print(ans)

Submission status: Runtime Error

Solution code:
# D
import numpy as np
N = int(input())
X = np.zeros(N, dtype=int)
Y = np.zeros(N, dtype=int)

for i in range(N):
    x, y = map(int, input().split())
    X[i] = x
    Y[i] = y

# edges
X_s = np.argsort(X)
Y_s = np.argsort(Y)

edge_list = []
edge_weight = []
for i in range(N-1):
    edge_list.append([X_s[i], X_s[i+1]])
    edge_weight.append(min(abs(X[X_s[i+1]] - X[X_s[i]]), abs(Y[X_s[i+1]] - Y[X_s[i]])))
    edge_list.append([Y_s[i], Y_s[i+1]])
    edge_weight.append(min(abs(X[Y_s[i+1]] - X[Y_s[i]]), abs(Y[Y_s[i+1]] - Y[Y_s[i]])))
    
# sort edges
sel = np.argsort(np.array(edge_weight))

# union find tree
uf = dict()
for i in range(N):
    uf[i] = i

res = 0
flg = np.zeros(N)

for s in sel:
    m, n = edge_list[s]
    # find union
    gr_m = m
    gr_m_list = []
    gr_n = n
    gr_n_list = []
    while gr_m != uf[gr_m]:
        gr_m_list.append(gr_m)
        gr_m = uf[gr_m]
    for m_ in gr_m_list:
        uf[m_] = gr_m
        
    while gr_n != uf[gr_n]:
        gr_n_list.append(gr_n)
        gr_n = uf[gr_n]
        
    for n_ in gr_n_list:
        uf[n_] = gr_n
    if gr_m == gr_n:
        pass
    else:
        res += edge_weight[s]
        if dep_m > dep_n:
            uf[gr_n] = gr_m
        elif dep_m > dep_n:
            uf[gr_n] = gr_m
        else:
            uf[gr_m] = gr_n
print(res)

Submission status: Runtime Error

Solution code:
# D
import numpy as np
N = int(input())
X = np.zeros(N, dtype=int)
Y = np.zeros(N, dtype=int)

for i in range(N):
    x, y = map(int, input().split())
    X[i] = x
    Y[i] = y

# edges
X_s = np.argsort(X)
Y_s = np.argsort(Y)

edge_list = []
edge_weight = []
for i in range(N-1):
    edge_list.append([X_s[i], X_s[i+1]])
    edge_weight.append(min(abs(X[X_s[i+1]] - X[X_s[i]]), abs(Y[X_s[i+1]] - Y[X_s[i]])))
    edge_list.append([Y_s[i], Y_s[i+1]])
    edge_weight.append(min(abs(X[Y_s[i+1]] - X[Y_s[i]]), abs(Y[Y_s[i+1]] - Y[Y_s[i]])))
    
# sort edges
sel = np.argsort(np.array(edge_weight))

# union find tree
uf = dict()
for i in range(N):
    uf[i] = i

res = 0
flg = np.zeros(N)

for s in sel:
    m, n = edge_list[s]
    # find union
    gr_m = m
    gr_m_list = []
    gr_n = n
    gr_n_list = []
    while gr_m != uf[gr_m]:
        gr_m_list.append(gr_m)
    for m_ in gr_m_list:
        uf[m_] = gr_m
    while gr_n != uf[gr_n]:
        gr_n_list.append(gr_n)
    for n_ in gr_n_list:
        uf[n_] = gr_n
    if gr_m == gr_n:
        pass
    else:
        res += edge_weight[s]
        if dep_m > dep_n:
            uf[gr_n] = gr_m
        elif dep_m > dep_n:
            uf[gr_n] = gr_m
        else:
            uf[gr_m] = gr_n
print(res)

Submission status: Runtime Error

Solution code:
vs = $stdin.each_line.drop(1).map { |row| row.split(' ').map { |c| c.to_i } }.map.with_index do |row, i|
  [i, row[0], row[1]]
end
v_new = []
v_new.push(vs.pop)

e_cost_sum = 0
while !vs.empty? do
  v = vs.pop
  edge_min = v_new.map { |u| [(u[1] - v[1]).abs, (u[2] - v[2]).abs].min }.min
  v_new.push(v)
  e_cost_sum += edge_min
end

puts e_cost_sum

Submission status: Runtime Error

Solution code:
from collections import defaultdict
n = input()
cs = []
for i in xrange(n):
    xi, yi = map(int, raw_input().split())
    cs.append((i, xi, yi))


csx = sorted(cs, key=lambda c: c[1])
csy = sorted(cs, key=lambda c: c[2])


xd = []
yd = []
for i in xrange(n-1):
    xd.append((csx[i+1][1] - csx[i][1], (csx[i], csx[i+1])))
    yd.append((csy[i+1][2] - csy[i][2], (csy[i], csy[i+1])))


diff = sorted(xd + yd)


res = 0
memo = defaultdict(int)
i = 0
c = 0

while c != n-1:
    if memo[diff[i][1][0][0]] >= 1 and memo[diff[i][1][1][0]] >= 1:
        i += 1
        continue
    memo[diff[i][1][0][0]] += 1
    memo[diff[i][1][1][0]] += 1
    res += diff[i][0]
    i += 1
    c += 1

print res

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

d = 10**9 + 7


def factorial(n):
    if (n > 1):
        return (n % d) * factorial(n-1)
    return 1


n, m = map(int, input().split())
ans = (factorial(n) % d) * (factorial(m) % d)
ans %= d
if n == m:
    ans *= 2

print(ans)