Submission #68783222

---

Source Code Expand

# E12 debug

import sys
import pprint
import numpy as np
from numba import jit, boolean, int64, float64, typeof, types, typeof, objmode




def main():
    from io import StringIO
    execute(StringIO(sample), sys.stderr)
    print("-- ^sample! --", file=sys.stderr)

    execute(sys.stdin, sys.stdout)

    if len(solve.nopython_signatures) != 1:
        raise KeyboardInterrupt("!! Unexpected: wrong use of jit !!")

def execute(src, dst):

    N, Q,  = map(int, src.readline().split())
    restnda = np.fromstring(src.read().strip(), dtype=np.int64, sep=' ')

    ans = solve(N, Q, restnda)
    print(*ans, sep="\n", file=dst)

sample = """\
5 12
3 2
2 2
3 2
1 2 5
1 3 4
3 4
3 5
1 4 5
1 1 3
3 1
2 2
3 1
"""

@jit(nopython=True, cache=True)
def solve(N, Q, restnda):
    # print(N, Q)
    Queries = []
    i = 0
    while i < len(restnda) :
        if restnda[i] == 1:
            Queries.append(restnda[i : i + 3])
            i += 3
        else:
            Queries.append(restnda[i : i + 2])
            i += 2
    # [print(q) for q in Queries]
    ans = []
    uf1 = UnionFindSX_int64(N+1)
    for query in Queries:
        # print(uf1.blacks , end="")
        if query[0] == 1:
            ty, u, v = query
            uf1.union(u, v)
            # print("union", u, v, uf1.findroot(u), uf1.findroot(v), end="")
        elif query[0] == 2:
            ty, v = query
            root = uf1.findroot(v)
            s = uf1.blacks[root]
            if v not in s:
                s.add(v)
            else:
                s.discard(v)
        elif query[0] == 3:
            ty, v = query
            root = uf1.findroot(v)
            s = uf1.blacks[root]
            if len(s) > 0 :
                res = "Yes"
            else:
                res = "No"
            ans.append(res)
            # print(v,root , res, end="")
        # print()
    # print(uf.findroot(2))
    # uf.union(1,2)
    # uf.union(1,3)
    # print(uf.findroot(3))
    return ans


#
import numba
try:
    from numba.experimental import jitclass
except ImportError:
    from numba import jitclass
spec_UF = [
    ("_table_size", types.int64[:]),
    ("blacks", types.List(types.Set(types.int64))),
]
@jitclass(spec_UF)
class UnionFindSX_int64():
    """サイズを保持, サイズ基準で結合, 要素id:int64 """
    """各グループがsetを保持"""
    def __init__(self, size):
        self._table_size = np.full((size,), -1, dtype=np.int64)
        self.blacks = [{-2, -3,} - {-2, -3,}  for _i in range(size)]
    def findroot(self, index):
        parent1 = self._table_size[index]
        if parent1 < 0:
            return index
        parent2 = self._table_size[parent1]
        if parent2 < 0:
            return parent1
        start = index
        depth = 1  # tocomp = depth - 1
        while True:
            depth += 1
            parentnext = self._table_size[parent2]
            if parentnext < 0:
                break
            parent2 = parentnext
        root = parent2
        update = start
        for _i in range(depth -1):
            parent = self._table_size[update]
            self._table_size[update] = root
            update = parent
        return root
    def union(self, x_index, y_index):
        root_L = self.findroot(x_index)
        root_S = self.findroot(y_index)
        if root_L == root_S:
            return False
        size_L = -self._table_size[root_L]
        size_S = -self._table_size[root_S]
        if size_L < size_S:
            (root_L, root_S,) = (root_S, root_L,)
        self._table_size[root_S] = root_L  # root を結合
        # if size_L == size_S:
        #     self._table_size[root_L] -= 1
        self._table_size[root_L] = -(size_S + size_L)
        for b_s in self.blacks[root_S]:
            self.blacks[root_L].add(b_s)
        return True

    def issame(self, x_index, y_index):
        return self.findroot(x_index) == self.findroot(y_index)
    def get_size(self, index):
        root = self.findroot(index)
        return -self._table_size[root]





main()

Submission Info

Judge Result