1 solutions

  • 0
    @ 2026-10-22 18:33:22

    C++ :

    undefined
    

    Java :

    undefined
    

    Python :

    # coding=utf-8
    import sys
    sys.setrecursionlimit(100000)
    
    class UnionFind:
        def __init__(self, size):
            self.parent = list(range(size + 1))  # 生物编号从1开始
            self.rank = [0] * (size + 1)  # 0:同层,1:父是上层,2:当前是父的上层
    
        def find(self, x):
            if self.parent[x] != x:
                orig_parent = self.parent[x]
                self.parent[x] = self.find(self.parent[x])
                # 更新关系:x到根的关系 = x到orig_parent的关系 + orig_parent到根的关系,模3
                self.rank[x] = (self.rank[x] + self.rank[orig_parent]) % 3
            return self.parent[x]
    
    n, k = map(int, sys.stdin.readline().split())
    uf = UnionFind(n)
    error = 0
    
    for _ in range(k):
        parts = sys.stdin.readline().split()
        op, M, X = parts[0], int(parts[1]), int(parts[2])
        
        # 错误情况2:M或X超过n
        if M > n or X > n:
            error += 1
            continue
        # 错误情况3:M==X且op是B
        if op == 'B' and M == X:
            error += 1
            continue
        
        root_m = uf.find(M)
        root_x = uf.find(X)
        
        if op == 'A':
            # 期望M和X同层(关系为0)
            if root_m == root_x:
                if (uf.rank[M] - uf.rank[X]) % 3 != 0:
                    error += 1
            else:
                # 合并:root_m的父设为root_x,调整rank使M和X同层
                uf.parent[root_m] = root_x
                uf.rank[root_m] = (uf.rank[X] - uf.rank[M]) % 3
        else:  # op == 'B',期望M是X的上层(M到X的关系为1)
            if root_m == root_x:
                if (uf.rank[M] - uf.rank[X] - 1) % 3 != 0:
                    error += 1
            else:
                # 合并:root_m的父设为root_x,调整rank使M是X的上层
                uf.parent[root_m] = root_x
                uf.rank[root_m] = (uf.rank[X] + 1 - uf.rank[M]) % 3
    
    print(error)
    
    • 1

    Information

    ID
    371
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    (None)
    # Submissions
    0
    Accepted
    0
    Uploaded By