Problem:


Score : 600 points

Problem Statement

There are N dots in a two-dimensional plane. The coordinates of the i-th dot are (x_i, y_i).

We will repeat the following operation as long as possible:

Choose four integers a, b, c, d (a \neq c, b \neq d) such that there are dots at exactly three of the positions (a, b), (a, d), (c, b) and (c, d), and add a dot at the remaining position.

We can prove that we can only do this operation a finite number of times. Find the maximum number of times we can do the operation.

Constraints

1 \leq N \leq 10^5

1 \leq x_i, y_i \leq 10^5

If i \neq j, x_i \neq x_j or y_i \neq y_j.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print the maximum number of times we can do the operation.

Sample Input 1

3
1 1
5 1
5 5

Sample Output 1

1

By choosing a = 1, b = 1, c = 5, d = 5, we can add a dot at (1, 5). We cannot do the operation any more, so the maximum number of operations is 1.

Sample Input 2

2
10 10
20 20

Sample Output 2

0

There are only two dots, so we cannot do the operation at all.

Sample Input 3

9
1 1
2 1
3 1
4 1
5 1
1 2
1 3
1 4
1 5

Sample Output 3

16

We can do the operation for all choices of the form a = 1, b = 1, c = i, d = j (2 \leq i,j \leq 5), and no more. Thus, the maximum number of operations is 16.



Sample input:
3
1 1
5 1
5 5


Sample output:
1

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    xy = []
    for _ in range(N):
        xy.append(LI())
    x2g = defaultdict(int)
    y2g = defaultdict(int)
    g2y = defaultdict(set)
    g2x = defaultdict(set)
    for x, y in xy:
        gx = x2g[x]
        gy = y2g[y]
        if gx != 0 and gy != 0:  # merge
            if len(g2x[gx]) + len(g2y[gx]) < len(g2x[gy]) + len(g2x[gy]):
                gx, gy = gy, gx
            for x in g2x[gy]:
                x2g[x] = gx
            for y in g2y[gy]:
                y2g[y] = gx
            g2y[gx] += g2y[gy]
            g2x[gx] += g2x[gy]
            g2y[gy] = set()
            g2x[gy] = set()
        else:
            g = x2g[x] or y2g[y] or x
            y2g[y] = g
            x2g[x] = g
            g2x[g].add(x)
            g2y[g].add(y)
    ans = -N
    for g in g2x.keys():
        ans += len(g2x[g]) * len(g2y[g])
    return ans

print(main())

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    x2g = defaultdict(int)
    y2g = defaultdict(int)
    g2y = defaultdict(set)
    g2x = defaultdict(set)
    for _ in range(N):
        x, y = LI()
        gx = x2g[x]
        gy = y2g[y]
        if gx != 0 and gy != 0:  # merge
            if len(g2x[gx]) + len(g2y[gx]) < len(g2x[gy]) + len(g2x[gy]):
                gx, gy = gy, gx
            g = gx
            for x in g2x[gy]:
                x2g[x] = g
            for y in g2y[gy]:
                y2g[y] = g
            g2y[g] += g2y[gy]
            g2x[g] += g2x[gy]
            g2y[gy] = set()
            g2x[gy] = set()
        else:
            g = x2g[x] or y2g[y] or x
            y2g[y] = g
            x2g[x] = g
            g2x[g].add(x)
            g2y[g].add(y)
    ans = -N
    for g in g2x.keys():
        ans += len(g2x[g]) * len(g2y[g])
    return ans

print(main())

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
N = int(input())
K = 10**5+1
P = [i for i in range(K)]

def par(a):
    if P[a] == a:
        return a
    t = par(P[a])
    P[a] = t
    return t
def cb(a, b):
    P[pa] = pb

X = [[] for _ in range(K)]
Y = [[] for _ in range(K)]
for _ in range(N):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    Y[y-1].append(x-1)
for i in range(K):
    for j in range(len(Y[i])-1):
        cb(Y[i][j], Y[i][j+1])

M = [[] for _ in range(K)]
for i in range(K):
    M[par(i)].append(i)
ans = -N
for i in range(K):
    S = []
    for j in M[i]:
        for k in X[j]:
            S.append(k)
    S = list(set(S))
    ans += len(S)*len(M[i])
print(ans)

Submission status: Runtime Error

Solution code:
def place(p_tuple):
    table.add(p_tuple)
    x, y = p_tuple
    ys = x_to_y[x]
    xs = y_to_x[y]

    if x in xs:
        xs.remove(x)
    if y in ys:
        ys.remove(y)

    # print(xs, ys)
    for x_i in xs:
        for y_i in ys:
            if (x_i, y_i) not in table:
                place((x_i, y_i))

    ys.add(y)
    xs.add(x)


num_plot = int(input())

plots_l = [tuple(map(int, input().split(' '))) for _ in range(0, num_plot)]
plots = set(sorted(plots_l))

table = set()
x_to_y = {i: set() for i in range(1, 10000)}
y_to_x = {i: set() for i in range(1, 10000)}

link_dict = {}

for plot in plots:
    if plot in table:
        continue
    place(plot)

for plot in plots:
    place(plot)

# print(table)
print(len(table) - len(plots))

Submission status: Runtime Error

Solution code:
def place(p_tuple):
    table.add(p_tuple)
    x, y = p_tuple
    ys = x_table[x]
    xs = y_table[y]

    if x in xs:
        xs.remove(x)
    if y in ys:
        ys.remove(y)

    # print(xs, ys)
    for x_i in xs:
        for y_i in ys:
            if (x_i, y_i) not in table:
                place((x_i, y_i))

    x_table[x].add(y)
    y_table[y].add(x)


num_plot = int(input())

plots_l = [tuple(map(int, input().split(' '))) for _ in range(0, num_plot)]
plots = set(sorted(plots_l))

table = set()
x_table = {i: set() for i in range(1, 10000)}
y_table = {i: set() for i in range(1, 10000)}

link_dict = {}

for plot in plots:
    if plot in table:
        continue
    place(plot)

for plot in plots:
    place(plot)

# print(table)
print(len(table) - len(plots))

Submission status: Runtime Error

Solution code:
n = int(input())
E = [[int(i) for i in input().split()] for j in range(n)]

X = [set() for i in range(10 ** 5 + 1)]
Y = [set() for i in range(10 ** 5 + 1)]

for x, y in E:
    X[x].add(y)
    Y[y].add(x)

ans = 0

used = [False] * (10 ** 5 + 1)

def dfs(x):
    if used[x]:
        return set()
    used[x] = True

    res = set(X[x])

    for y in X[x]:
        for a in Y[y]:
            res |= dfs(a)

    return res

used2 = [False] * (10 ** 5 + 1)

def dfs2(S, x):
    if used2[x]:
        return 0
    used2[x] = True

    res = 0
    
    for y in X[x]:
        for a in Y[y]:
            res += dfs2(S, a)

    return res + len(S - X[x])


for i, x in enumerate(X):
    if len(x) < 2:
        continue
    S = dfs(i)
    ans += dfs2(S, i)

print(ans)

Submission status: Runtime Error

Solution code:
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b

A, B, C, D = map(int, input().split())
E = C * D // gcd(C, D)

divc = B // C - (A - 1) // C
divd = B // D - (A - 1) // D
dive = B // E  - (A - 1) // E

print(B + 1 - A - (divc + divd - dive))

Submission status: Runtime Error

Solution code:
import sys
# input = sys.stdin.readline

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

xset = set([])
yset = set([])

for xi, yi in xy:
    xset.add(xi)
    yset.add(yi)

xmap = {}
ymap = {}
for i, xi in enumerate(xset):
    xmap[str(xi)] = i
for i, yi in enumerate(yset):
    ymap[str(yi)] = i
# print("#", xmap, ymap)

xcnt = [0] * len(xset)
ycnt = [0] * len(yset)
xycnt = [[0] * len(xset) for _ in range(len(yset))]
for i, (xi, yi) in enumerate(xy):
    xcnt[xmap[str(xi)]] += 1
    ycnt[ymap[str(yi)]] += 1

ans_x = [True] * len(xset)
ans_y = [True] * len(yset)
for i in range(len(yset)):
    for j in range(len(yset)):
        if xcnt[i] == 1 and ycnt[j] == 1:
            ans_x[i] = False
            ans_y[j] = False

ans = 0
for i in range(len(xset)):
    if ans_x == False: continue
    ans += len(yset)
    ans -= xcnt[i]

print(ans)

Submission status: Runtime Error

Solution code:
from operator import itemgetter
n = int(input())
a = [[int(i) for i in input().split()] for i in range(n)]
a = sorted(a)
ac_num = collections.Counter(a[:][0])
bd_num = collections.Counter(a[:][1])
ans = 0
for i in range(n):
  a_num = a[i][0]
  b_num = a[i][1]
  c_num = -1
  d_num = -1
  c_tmp = -1
  d_tmp = -1
  for i in range(n):
    if a[i][0] is a_num and a[i][1] is not b_num:
      d_num = a[i][1]
      d_tmp = a[i][0]
    elif a[i][0] is not a_num and a[i][1] is b_num:
      c_num = a[i][0]
      c_tmp = a[i][1]
  if c_num is not -1 and d_num is not -1:
    ans += 1
    for i in range(n):
      if a[i][0] is c_num and a[i][1] is not d_num:
        ans -= 1
  elif c_num is not -1:
    for i in range(n):
      if a[i][0] is d_tmp and a[i][1] is not d_num:
        ans += 1
  elif d_num is not -1:
    for i in range(n):
      if a[i][1] is c_tmp and a[i][0] is not c_num:
        ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
X, Y = {}, {}
for _ in range(N):
    inp = input().split()
    if inp[0] in X:
        X[inp[0]].append(inp[1])
    else:
        X[inp[0]] = [inp[1]]
    if inp[1] in Y:
        Y[inp[1]].append(inp[0])
    else:
        Y[inp[1]] = [inp[0]]

cnt = 0
while True:
    cnt_ = 0
    X_ = Y.values()
    len_X_ = len(X_)
    for i in range(len_X_):
        for j in range(len_X_):
            for y in X[i]:
                if y not in X[j]:
                    cnt_ += 1
                    X[j].append(y)
                    Y[y].append(j)
    cnt += cnt_
    if cnt_ == 0:
        break

print(cnt)

Submission status: Runtime Error

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for _ in range(N)]

M = 10 * 5 + 1
D = [[0] * M for _ in range(M)]

X = {}
Y = {}
for x, y in xy:
  if x in X:
    X[x].append(y)
  else:
    X[x] = [y]
  if y in Y:
    Y[y].append(x)
  else:
    Y[y] = [x]
  D[x][y] = 1

ans = 0
for xx in X.keys():
  x = X[xx]
  L = len(x)
  if L == 1: continue
  for i in range(L - 1):
    if x[i] not in Y: continue
    y = Y[x[i]]
    for j in range(i + 1, L):
      for k in y:
        if D[k][x[j]] == 0:
          ans += 1

print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
dot = {}
dotset = set()
for i in range(n):
    x, y = map(int, input().split())
    dot[i] = (x, y)
    dotset.add((x, y))

v = set()

cnt = 0
for i, f in dot:
    a, b = f
    for j, g in dot:
        if i == j: continue
        c, d = g
        if a == c or b == d: continue
        f1 = (a, d) in dotset
        f2 = (c, b) in dotset
        if f1 and not f2:
            cnt += 1
            dotset.add((c, b))
        if not f1 and f2:
            cnt += 1
            dotset.add((a, d))
print(cnt)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def YesNo(x): return 'Yes' if x else 'No'
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import defaultdict

def main():
    N = II()
    edges = defaultdict(list)
    for _ in range(N):
        x, y = LI()
        edges[x].append(-y)
        edges[-y].append(x)
    visited = [0] * (N * 2 + 10)
    def solve(v):
        visited[v] = 1
        ret = [v]
        for u in edges[v]:
            if not visited[u]:
                ret += solve(u)
        return ret
    ans = -N
    for node in edges:
        if not visited[node]:
            li = solve(node)
            m, p = 0, 0
            for z in li:
                if z < 0:
                    m += 1
                else:
                    p += 1
            ans += m * p
    return ans

print(main())