Problem p02998 (python)

Fixed submission:
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())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        y = -y
        gx = xy2g[x]
        gy = xy2g[y]
        if gx != 0 and gy != 0:  # merge
            if gx == gy:
                continue
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[y] = g
            g2xy[g] |= {x, y}
    ans = -N
    for xys in g2xy.values():
        m, p = 0, 0
        for xy in xys:
            if xy < 0:
                m += 1
            else:
                p += 1
        ans += m * p
    return ans

print(main())

Buggy submission (verdict: Runtime Error):
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())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        gx = xy2g[x]
        gy = xy2g[-y]
        if gx != 0 and gy != 0:  # merge
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gx] += {x, -y}
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[-y] = g
            g2xy[g] |= {x, -y}
    ans = -N
    for xys in g2xy.values():
        m, p = 0, 0
        for xy in xys:
            if xy < 0:
                m += 1
            else:
                p += 1
        ans += m * p
    return ans

print(main())

Buggy submission (verdict: Runtime Error):
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())
    xy2g = defaultdict(int)
    g2xy = defaultdict(set)
    for x, y in xy:
        gx = xy2g[x]
        gy = xy2g[-y]
        if gx != 0 and gy != 0:  # merge
            if len(g2xy[gx]) < len(g2xy[gy]):
                gx, gy = gy, gx
            for xy in g2xy[gy]:
                xy2g[xy] = gx
            g2xy[gx] |= g2xy[gy]
            g2xy[gy].clear()
        else:
            g = gx or gy or x
            xy2g[x] = xy2g[-y] = g
            g2xy[g] |= {x, -y}
    ans = -N
    for xys in g2xy.values():
        m, p = 0, 0
        for xy in xys:
            if xy < 0:
                m += 1
            else:
                p += 1
        if m == 0 and p != 0:
            1 = 1
        elif m != 0 and p == 0:
            1 = 1
        ans += m * p
    return ans

print(main())

Buggy submission (verdict: Runtime Error):
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())

Buggy submission (verdict: Runtime Error):
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())

Buggy submission (verdict: Runtime Error):
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())

Buggy submission (verdict: Runtime Error):
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())

Buggy submission (verdict: Runtime Error):
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())