1 solutions
-
0
C++ :
undefinedJava :
undefinedPython :
# 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