ABC409 E — Pair Annihilation

1# -*- coding: utf-8 -*-2 3 4class UnionFind:5    """Represents a data structure that tracks a set of elements partitioned6       into a number of disjoint (non-overlapping) subsets.7 8    Landau notation: O(α(n)), where α(n) is the inverse Ackermann function.9 10    See:11    https://www.youtube.com/watch?v=zV3Ul2pA2Fw12    https://en.wikipedia.org/wiki/Disjoint-set_data_structure13    https://atcoder.jp/contests/abc120/submissions/444494214    https://atcoder.jp/contests/abc292/submissions/3941007515    https://github.com/not522/ac-library-python/blob/master/atcoder/dsu.py16    """17 18    def __init__(self, number_count: int) -> None:19        """20        Args:21            number_count: The size of elements (greater than 2).22        """23        self.number_count = number_count24        self.parent_numbers = [-1 for _ in range(number_count)]25        self.edge_count = [0 for _ in range(number_count)]26        self.group_count = number_count27 28    def find_root(self, number: int) -> int:29        """Follows the chain of parent pointers from number up the tree until30           it reaches a root element, whose parent is itself.31        Args:32            number: The trees id (0-index).33 34        Returns:35            The index of a root element.36        """37        if self.parent_numbers[number] < 0:38            return number39 40        self.parent_numbers[number] = self.find_root(self.parent_numbers[number])41        return self.parent_numbers[number]42 43    def get_group_size(self, number: int) -> int:44        """45        Args:46            number: The trees id (0-index).47 48        Returns:49            The size of group.50        """51        return -self.parent_numbers[self.find_root(number)]52 53    def is_same_group(self, number_x: int, number_y: int) -> bool:54        """Represents the roots of tree number_x and number_y are in the same55           group.56        Args:57            number_x: The trees x (0-index).58            number_y: The trees y (0-index).59        """60        return self.find_root(number_x) == self.find_root(number_y)61 62    def merge_if_needs(self, number_x: int, number_y: int) -> bool:63        """Uses find_root to determine the roots of the tree number_x and64           number_y belong to. If the roots are distinct, the trees are combined65           by attaching the roots of one to the root of the other.66        Args:67            number_x: The trees x (0-index).68            number_y: The trees y (0-index).69        """70        x = self.find_root(number_x)71        y = self.find_root(number_y)72 73        self.edge_count[x] += 174 75        if x == y:76            return False77 78        self.group_count -= 179 80        if self.parent_numbers[x] > self.parent_numbers[y]:81            x, y = y, x82 83        self.parent_numbers[x] += self.parent_numbers[y]84        self.parent_numbers[y] = x85        self.edge_count[x] += self.edge_count[y]86        return True87 88 89def main():90    import sys91 92    input = sys.stdin.readline93 94    n, m = map(int, input().split())95    edges = list()96 97    for _ in range(m):98        ai, bi, ci = map(int, input().split())99        ai -= 1100        bi -= 1101        edges.append((ai, bi, ci))102 103    # 上の桁から0にできるかどうか + 条件を満たす辺で構成されるグラフの連結性を判定104    ans = 0105 106    for digit in range(29, -1, -1):107        uf = UnionFind(n)108 109        for ai, bi, ci in edges:110            # 辺のコストの末尾digit桁を削ったときに、答えの候補となっているビットを満たしているか?111            if ((ci >> digit) | (ans >> digit)) != (ans >> digit):112                continue113 114            uf.merge_if_needs(ai, bi)115 116        # 始点と終点が同じ連結成分にない場合は、答えのi桁目のビットを立てる117        if not uf.is_same_group(0, n - 1):118            ans |= 1 << digit119 120    print(ans)121 122 123if __name__ == "__main__":124    main()125