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: Wrong Answer

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)
    g2c = defaultdict(int)
    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(g2y[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()
            g2c[gx] += g2c[gy] + 1
            g2c[gy] = 0
        else:
            g = gx or gy or x
            x2g[x] = g
            y2g[y] = g
            g2x[g].add(x)
            g2y[g].add(y)
            g2c[g] += 1
    ans = 0
    for g in g2x.keys():
        if len(g2x[g]) > 1 and len(g2y[g]) > 1:
            ans += len(g2x[g]) * len(g2y[g]) - g2c[g]
    return ans

print(main())

Submission status: Wrong Answer

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)
    g2c = defaultdict(int)
    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(g2y[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()
            g2c[gx] += g2c[gy] + 1
            g2c[gy] = 0
        else:
            g = gx or gy or x
            x2g[x] = g
            y2g[y] = g
            g2x[g].add(x)
            g2y[g].add(y)
            g2c[g] += 1
    ans = 0
    for g in g2x.keys():
        if g2x[g]:
            ans += len(g2x[g]) * len(g2y[g]) - g2c[g]
    return ans

print(main())

Submission status: Wrong Answer

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(g2y[gy]):
                gx, gy = gy, gx
            for x in g2x[gy]:
                x2g[x] = gx
            for y in g2y[gy]:
                y2g[y] = gx
            g2y[gx] = g2y[gx] | g2y[gy]
            g2x[gx] = g2x[gx] | g2x[gy]
            g2y[gy] = set()
            g2x[gy] = set()
        else:
            g = gx or gy or x
            x2g[x] = g
            y2g[y] = g
            g2x[g].add(x)
            g2y[g].add(y)
    ans = -N
    for g in g2x.keys():
        if g2x[g]:
            ans += len(g2x[g]) * len(g2y[g])
    return ans

print(main())

Submission status: Wrong Answer

Solution code:
def main():
     def root(x):
          path=[]
          while x!=P[x]:
               path.append(x)
               x=P[x]
          for i in path:
               P[i]=x
          return x

     def unite(x,y):
          a,b=max(root(x),root(y)),min(root(x),root(y))
          P[a]=b
     
     n=int(input())
     P=[i for i in range(n)]
     field=[]
     for i in range(n):
          x,y=map(int,input().split())
          field.append([x,y,i])
          
     
     field.sort(key=lambda x:x[0])
     for i in range(n-1):
          if field[i][0]==field[i+1][0]:
               unite(field[i][2],field[i+1][2])
     
     field.sort(key=lambda x:x[1])
     for i in range(n-1):
          if field[i][1]==field[i+1][1]:
               unite(field[i][2],field[i+1][2])
     
     cnt=0
     for i in range(n):
          X=[]
          Y=[]
          for j in range(n):
               if i==root(j):
                    x,y=field[j][0],field[j][1]
                    if x not in X:
                         X.append(x)
                    if y not in Y:
                         Y.append(y)
          cnt+=len(X)*len(Y)
          #print(i,X,Y)
     print(cnt-n)
                    
     
if __name__=='__main__':
     main()

Submission status: Wrong Answer

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(g2y[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 = gx or gy or x
            x2g[x] = g
            y2g[y] = g
            g2x[g].add(x)
            g2y[g].add(y)
    ans = -N
    for g in g2x.keys():
        if g2x[g]:
            ans += len(g2x[g]) * len(g2y[g])
    return ans

print(main())

Submission status: Wrong Answer

Solution code:
def main():
     def root(x):
          path=[]
          while x!=P[x]:
               path.append(x)
               x=P[x]
          for i in path:
               P[i]=x
          return x

     def unite(x,y):
          a,b=max(root(x),root(y)),min(root(x),root(y))
          P[a]=b
     
     n=int(input())
     P=[i for i in range(n)]
     field=[]
     for i in range(n):
          x,y=map(int,input().split())
          field.append([x,y,i])
          
     
     field.sort(key=lambda x:x[0])
     for i in range(n-1):
          if field[i][0]==field[i+1][0]:
               unite(field[i][2],field[i+1][2])
     
     field.sort(key=lambda x:x[1])
     for i in range(n-1):
          if field[i][1]==field[i+1][1]:
               unite(field[i][2],field[i+1][2])
     #print(P)
     
     cnt=0
     for i in range(n):
          X=[]
          Y=[]
          for j in range(n):
               if i==P[j]:
                    x,y=field[j][0],field[j][1]
                    if x not in X:
                         X.append(x)
                    if y not in Y:
                         Y.append(y)
          cnt+=len(X)*len(Y)
          #print(i,X,Y)
     print(cnt-n)
                    
     
if __name__=='__main__':
     main()

Submission status: Wrong Answer

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(g2y[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()
        elif gx > 0:
            y2g[y] = gx
            g2y[gx].add(y)
        elif gy > 0:
            x2g[x] = gy
            g2x[gy].add(x)
        else:
            x2g[x] = x
            y2g[y] = x
            g2x[x].add(x)
            g2y[x].add(y)
    ans = -N
    for g in g2x.keys():
        if g2x[g]:
            ans += len(g2x[g]) * len(g2y[g])
    return ans

print(main())

Submission status: Wrong Answer

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()
        elif gx > 0:
            y2g[y] = gx
            g2y[gx].add(y)
        elif gy > 0:
            x2g[x] = gy
            g2x[gy].add(x)
        else:
            x2g[x] = x
            y2g[y] = x
            g2x[x].add(x)
            g2y[x].add(y)
    ans = -N
    for g in g2x.keys():
        if g2x[g]:
            ans += len(g2x[g]) * len(g2y[g])
    return ans

print(main())

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    s = S()
    for i in range(len(s)-1):
        if s[i] == s[i+1]:
            print("Bad")
            quit()
    print("Good")
    return

#B
def B():
    n,l = LI()
    a = [i+l for i in range(n)]
    ans = sum(a)
    m = n+l-1
    for i in a[::-1]:
        if i < 0:break
        m = min(m,i)
    ans -= m
    print(ans)
    return

#C
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
def C():
    a,b,c,d = LI()
    g = gcd(c,d)
    l = c*d//g
    sc = b//c-(a-1)//c
    sd = b//d-(a-1)//d
    sl = b//l-(a-1)//l
    print(b-a+1-sc-sd+sl)
    return

#D
def D():
    n = I()
    w = LIR(n)
    w.sort(key = lambda x: x[1])
    t = 0
    for a,b in w:
        if t+a > b:
            print("No")
            quit()
        t += a
    print("Yes")
    return

#E
def E():
    n,k = LI()
    if k == 0:
        m = (n*(n-1))//2
        print(m)
        for i in range(1,n+1):
            for j in range(i+1,n+1):
                print(i,j)
    else:
        if k > ((n-1)*(n-2))//2:
            print(-1)
        else:
            ans = []
            for i in range(2,n+1):
                ans.append((1,i))
            m = ((n-1)*(n-2))//2
            for i in range(2,n+1):
                for j in range(i+1,n+1):
                    if m == k:break
                    ans.append((i,j))
                    m -= 1
                if m == k:break
            print(len(ans))
            for i,j in ans:
                print(i,j)
    return

#F
def F():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]
    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
    n = I()
    v = defaultdict(list)
    h = defaultdict(list)
    par = defaultdict(int)
    rank = defaultdict(int)
    for i in range(n):
        a,b = LI()
        v[a].append(b)
        h[b].append(a)
        par[a] = a
        rank[a] = 0
    h = h.values()
    for l in h:
        for i in range(len(l)-1):
            x = l[i]
            y = l[i+1]
            if root(x) != root(y):
                unite(x,y)
    h = defaultdict(list)
    for i in par.keys():
        par[i] = root(par[i])
        h[par[i]].append(i)
    h = h.values()
    ans = 0
    for k in h:
        f = defaultdict(lambda : 0)
        m = 0
        for i in k:
            for j in v[i]:
                if not f[j]:
                    m += 1
                    f[j] = 1
        for i in v.keys():
            ans += m-len(v[i])
    print(ans)
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    s = S()
    for i in range(len(s)-1):
        if s[i] == s[i+1]:
            print("Bad")
            quit()
    print("Good")
    return

#B
def B():
    n,l = LI()
    a = [i+l for i in range(n)]
    ans = sum(a)
    m = n+l-1
    for i in a[::-1]:
        if i < 0:break
        m = min(m,i)
    ans -= m
    print(ans)
    return

#C
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b%a,a)
def C():
    a,b,c,d = LI()
    g = gcd(c,d)
    l = c*d//g
    sc = b//c-(a-1)//c
    sd = b//d-(a-1)//d
    sl = b//l-(a-1)//l
    print(b-a+1-sc-sd+sl)
    return

#D
def D():
    n = I()
    w = LIR(n)
    w.sort(key = lambda x: x[1])
    t = 0
    for a,b in w:
        if t+a > b:
            print("No")
            quit()
        t += a
    print("Yes")
    return

#E
def E():
    n,k = LI()
    if k == 0:
        m = (n*(n-1))//2
        print(m)
        for i in range(1,n+1):
            for j in range(i+1,n+1):
                print(i,j)
    else:
        if k > ((n-1)*(n-2))//2:
            print(-1)
        else:
            ans = []
            for i in range(2,n+1):
                ans.append((1,i))
            m = ((n-1)*(n-2))//2
            for i in range(2,n+1):
                for j in range(i+1,n+1):
                    if m == k:break
                    ans.append((i,j))
                    m -= 1
                if m == k:break
            print(len(ans))
            for i,j in ans:
                print(i,j)
    return

#F
def F():
    def root(x):
        if par[x] == x:
            return x
        par[x] = root(par[x])
        return par[x]
    def unite(x,y):
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
    n = I()
    v = defaultdict(list)
    h = defaultdict(list)
    par = defaultdict(int)
    rank = defaultdict(int)
    for i in range(n):
        a,b = LI()
        v[a].append(b)
        h[b].append(a)
        par[a] = a
        rank[a] = 0
    h = h.values()
    for l in h:
        for i in range(len(l)-1):
            x = l[i]
            y = l[i+1]
            if root(x) != root(y):
                unite(x,y)
    h = defaultdict(list)
    for i in par.keys():
        par[i] = root(par[i])
        h[par[i]].append(i)
    h = h.values()
    ans = 0
    for k in h:
        f = defaultdict(lambda : 0)
        m = 0
        for i in k:
            for j in v[i]:
                if not f[j]:
                    m += 1
                    f[j] = 1
        for i in f:
            ans += m-len(v[i])
    print(ans)
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Wrong Answer

Solution code:
N = int(input())
e = [[int(i) for i in input().split()] for i in range(N)]

from operator import itemgetter
              
se = sorted(e, key=itemgetter(1))
if N <= 2:
	print(0)

stmp = []
for i in range(N):
	tmp = se.copy()
	tmpa = []
	tmpb = []
	tmp.pop(i)
	tmpa = list(set([x[0] for x in tmp]))
	tmpb = list(set([x[1] for x in tmp]))
	#print(tmpa)
	#print(tmpb)
	#print(se)
	if se[i][0] not in tmpa and se[i][1] not in tmpb:
		stmp.append(se[i])
nse = []
stmp.append([-1,-1])
erg = set(map(tuple,se))
ehb = set(map(tuple, stmp))
nse = erg.difference(ehb)
#print(list(nse))
#print([[x[0],x[1]] for x in nse])
print(len(list(set([x[0] for x in nse]))) * len(list(set([x[1] for x in nse]))) - len(nse))

Submission status: Wrong Answer

Solution code:
N = int(input())
XY = [tuple([int(_) for _ in input().split()]) for i in range(N)]

import sys
sys.setrecursionlimit(10000)

from collections import defaultdict

p = set()

px = defaultdict(list)
py = defaultdict(list)

def addp(x, y):
    if (x, y) in p:
        return
    p.add((x, y))
    for i in px[x]:
        for j in py[i]:
            addp(j, y)
    for j in py[y]:
        for i in px[j]:
            addp(x, i)
    px[x].append(y)
    py[y].append(x)


for x, y in XY:
    # print(p, px ,py)
    addp(x, y)

print(len(p) - N)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n = int(input())
dx = defaultdict(list)
dy = defaultdict(list)
pts = []
for _ in range(n):
    x, y = map(int, input().split())
    dx[x].append(y)
    dy[y].append(x)
    pts.append((x, y))

vx, vy = set(), set()
cnt = 0
for x, y in pts:
    if x in vx or y in vy: continue
    sx, sy = [x], [y]
    xs, ys = set(), set()
    while sx or sy:
        while sx:
            x = sx.pop()
            if x not in xs:
                xs.add(x)
                for y in dx[x]:
                    if y not in ys:
                        sy.append(y)
        while sy:
            y = sy.pop()
            if y not in ys:
                ys.add(y)
                for x in dy[y]:
                    if x not in xs:
                        sx.append(x)
    vx.update(dx)
    vy.update(dy)
    cnt += len(dx) * len(dy)
print(cnt - len(pts))

Submission status: Wrong Answer

Solution code:
N = int(input())
e = [[int(i) for i in input().split()] for i in range(N)]

from operator import itemgetter
              
se = sorted(e, key=itemgetter(1))
if N <= 2:
	print(0)

stmp = []
for i in range(N):
	tmp = se.copy()
	tmpa = []
	tmpb = []
	tmp.pop(i)
	tmpa = list(set([x[0] for x in tmp]))
	tmpb = list(set([x[1] for x in tmp]))
	#print(tmpa)
	#print(tmpb)
	#print(se)
	if se[i][0] not in tmpa and se[i][1] not in tmpb:
		stmp.append(se[i])
nse = []
stmp.append([-1,-1])
erg = set(map(tuple,se))
ehb = set(map(tuple, stmp))
nse = erg.difference(ehb)
#print(nse)

print(len(list(set([x[0] for x in nse]))) * len(list(set([x[1] for x in nse]))) - len(nse))

Submission status: Wrong Answer

Solution code:
N = int(input())
xs = {}
ys = {}
for i in range(N):
    pair = tuple(map(int,input().split()))
    if pair[0] not in xs:
        xs[pair[0]] = []
    xs[pair[0]].append(pair)
    if pair[1] not in ys:
        ys[pair[1]] = []
    ys[pair[1]].append(pair)
# print(xs)
# print(ys)

newy = set()
sumix = set()
sumiy = set()
sumi = set()
for k in xs:
    if len(xs[k]) > 1:
        for pair in xs[k]:
            newy.add(pair[1])
            sumiy.add(pair[1])
            sumi.add(pair)
        sumiy.add(k)
newx = set()
while True:
    for y in newy:
        for pair in ys[y]:
            if pair[0] not in sumix:
                newx.add(pair[0])
                sumix.add(pair[0])
                sumi.add(pair)
    # print(newx)
    newy = set()
    for x in newx:
        for pair in xs[x]:
            if pair[1] not in sumiy:
                newy.add(pair[1])
                sumiy.add(pair[1])
                sumi.add(pair)
    if newy == set():
        break



for k in ys:
    if len(ys[k]) > 1:
        for pair in ys[k]:
            newx.add(pair[0])
            sumix.add(pair[0])
            sumi.add(pair)
        sumix.add(k)
newy = set()
while True:
    for x in newx:
        for pair in xs[x]:
            if pair[1] not in sumiy:
                newy.add(pair[1])
                sumiy.add(pair[1])
                sumi.add(pair)
    # print(newx)
    newx = set()
    for y in newy:
        for pair in ys[y]:
            if pair[0] not in sumix:
                newx.add(pair[0])
                sumix.add(pair[0])
                sumi.add(pair)
    if newx == set():
        break





if sumi == set():
    print(0)
    exit()
ssx = sorted(sumix)
xran = len(ssx)
ssy = sorted(sumiy)
yran = len(ssy)
print(xran*yran-len(sumi))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n = int(input())
dx = defaultdict(list)
dy = defaultdict(list)
pts = []
for _ in range(n):
    x, y = map(int, input().split())
    dx[x].append(y)
    dy[y].append(x)
    pts.append((x, y))

vx, vy = set(), set()
cnt = 0
for x, y in pts:
    sx, sy = [x], [y]
    xs, ys = set(), set()
    while sx or sy:
        while sx:
            x = sx.pop()
            if x not in xs:
                xs.add(x)
                for y in dx[x]:
                    if y not in ys:
                        sy.append(y)
        while sy:
            y = sy.pop()
            if y not in ys:
                ys.add(y)
                for x in dy[y]:
                    if x not in xs:
                        sx.append(x)
    vx.update(dx)
    vy.update(dy)
    cnt += len(dx) * len(dy)
print(cnt - len(pts))

Submission status: Wrong Answer

Solution code:
N = int(input())
X = {}
Y = {}
P = [False] * N

LX = set()
LY = set()
for n in range(N):
    x, y = map(int, input().split())
    X.setdefault(x, []).append((n, x, y))
    Y.setdefault(y, []).append((n, x, y))

for x0, lx in X.items():
    if len(lx) < 2:
        continue

    can_make = False
    ns = set()
    lys = set()
    for n, x, y in lx:
        ns.add(n)
        lys.add(y)
        if len(Y[y]) > 1:
            can_make = True

    if can_make:
        for n in ns:
            P[n] = True
        LX.add(x0)
        LY |= lys

for y0, ly in Y.items():
    if len(ly) < 2:
        continue

    can_make = False
    ns = set()
    lxs = set()
    for n, x, y in ly:
        ns.add(n)
        lxs.add(x)
        if len(X[x]) > 1:
            can_make = True
    if can_make:
        for n in ns:
            P[n] = True
        LX |= lxs
        LY.add(y0)

print(len(LX) * len(LY) - P.count(True))

Submission status: Wrong Answer

Solution code:
N = int(input())
P = [None] * N
Q = set()
for n in range(N):
	P[n] = tuple(map(int,input().split()))
	Q.add(P[n])

ans = 0

T = range(N)
s = -1
for w in P:
	s += 1
	x = P[s][0]
	y = P[s][1]
	for t in range(s+1,len(P)):
		p = P[t][0] - x
		q = P[t][1] - y
		if p == 0 and q != 0:
			if {(x+q,y)} <= Q and Q.isdisjoint({(x+q,y+q)}):
				ans += 1
				Q.add((x+q,y+q))
				P.append((x+q,y+q))
			elif {(x+q,y+q)} <= Q and Q.isdisjoint({(x+q,y)}):
				ans += 1
				Q.add((x+q,y))
				P.append((x+q,y))
		elif p != 0 and q == 0:
			if {(x,y+p)} <= Q and Q.isdisjoint({(x+p,y+p)}):
				ans += 1
				Q.add((x+p,y+p))
				P.append((x+q,y+q))
			elif {(x+p,y+p)} <= Q and Q.isdisjoint({(x,y+p)}):
				ans += 1
				Q.add((x,y+p))
				P.append((x,y+q))
		elif p == q and p != 0:
			if {(x+p,y)} <= Q and Q.isdisjoint({(x, y+p)}):
				ans += 1
				Q.add((x+p,y+p))
				P.append((x+q,y+q))
			elif {(x,y+p)} <= Q and Q.isdisjoint({(x+p,y)}):
				ans += 1
				Q.add((x+p,y))
				P.append((x+q,y))
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

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

X.sort(key = lambda x:x[0])
Y = []

count = -1
prev = -1
for i in range(N):
    if X[i][0] != prev:
        count+=1
        Y.append([count,X[i][1]])
        prev=X[i][0]
    else:
        Y.append([count,X[i][1]])

Y.sort(key = lambda x:x[1])

group_list = [-1 for i in range(count+1)]
group_list[Y[0][0]] = 0
count = 0
dg = Y[0][0]
prev = Y[0][1]
for i in range(1,N):
    if Y[i][1] == prev:
        if group_list[Y[i][0]]==-1:
            group_list[Y[i][0]]=count
    else:
        prev = Y[i][1]
        count+=1
        if group_list[Y[i][0]]==-1:
            group_list[Y[i][0]]=count
color_list = []
for i in range(N):
    color_list.append(group_list[Y[i][0]])

index=max(color_list)
A=[[[],[]] for i in range(index+1)]
for i in range(N):
    A[color_list[i]][0].append(Y[i][0])
    A[color_list[i]][1].append(Y[i][1])
s = 0
for a in A:
    s += len(set(a[0]))*len(set(a[1]))

print(s-N)

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
#n, k = [int(i) for i in input().split()]
table = [[int(i) for i in input().split()] for j in range(n)]
#table = [list(input()) for n in range(h)]
#list = [int(i) for i in input().split()]
#num = [int(i) for i in range(n)]
#s = input()
#list = list(s)


table2 = sorted(table, key=lambda x:(x[0],x[1]))

kotae = 0

for i in range(n - 1) :
    for j in range(1, n - i) :
        if(table2[i][0] == table2[i+j][0]) :
            for k in range(0, n) :
                if((table2[i][1] == table2[k][1]) and (i != k) and (i + j != k)) :
                    kotae += 1
                if((table2[i+j][1] == table2[k][1]) and (i != k) and (i + j != k)) :
                    kotae += 1
        else :
            break

print(kotae)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
xy = [list(map(int, input().split())) for i in range(n)]
xy.sort(key=lambda x:(x[0], x[1]))

used_y = set()
used = False
start = xy[0][0]
before = xy[0][0]
ans = 0
cnt = 0
top = False
for x, y in xy:
    if before != x:
        before= x
        used = False
        cnt = 1
        top = False
    if y in used_y:
        if used:
            if x != start:
                ans -= 1
        else:
            if x != start:
                ans += len(used_y) - cnt
            used = True
        top = True
    else:
        used_y.add(y)
        cnt += 1
        if x != start and top:
            ans += 1
        top +=1
print(ans)

Submission status: Wrong Answer

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

cnt = 0
while True:
    cnt_ = 0
    for x_i in X_to_Y.keys():
        for x_j in X_to_Y.keys():
            for y in X_to_Y[x_i]:
                if y not in X_to_Y[x_j]:
                    cnt_ += 1
                    X_to_Y[x_j].append(y)
    cnt += cnt_
    if cnt_ == 0:
        break

print(cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
X = {}
Y = {}
P = [False] * N

LX = set()
LY = set()
for n in range(N):
    x, y = map(int, input().split())
    X.setdefault(x, []).append((n, x, y))
    Y.setdefault(y, []).append((n, x, y))

can_make = False
for x0, lx in X.items():
    if len(lx) < 2:
        continue

    LX.add(x0)
    for n, x, y in lx:
        P[n] = True
        if y in LY:
            can_make = True
        LY.add(y)
        ly = Y[y]
        if len(ly) == 1:
            n1, _, _ = ly[0]
            P[n1] = True

for y0, ly in Y.items():
    if len(ly) < 2:
        continue

    LY.add(y0)
    for n, x, y in ly:
        P[n] = True
        LX.add(x)
        lx = X[x]
        if len(lx) == 1:
            n1, _, _ = lx[0]
            P[n1] = True

print(len(LX) * len(LY) - P.count(True) if can_make else 0)