ABC363 E — Sinking Land

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    from collections import defaultdict92 93    input = sys.stdin.readline94 95    h, w, y = map(int, input().split())96    pos = defaultdict(list)97 98    for i in range(h):99        ai = list(map(int, input().split()))100 101        for j, aij in enumerate(ai):102            if aij <= y:103                # 0年スタートに104                pos[aij - 1].append((i, j))105 106    under_sea = [[False for _ in range(w)] for _ in range(h)]107    size = h * w108    # 海を超頂点として持つ109    uf = UnionFind(size + 1)110    dxy = [(-1, 0), (1, 0), (0, -1), (0, 1), (-1, -1), (1, -1), (-1, 1), (1, 1)]111    dxy = dxy[:4]112 113    for year in range(y):114        for i, j in pos[year]:115            under_sea[i][j] = True116            v = i * w + j117 118            for dx, dy in dxy:119                ni = i + dy120                nj = j + dx121 122                # 海かどうかの判定123                if ni < 0 or ni >= h or nj < 0 or nj >= w:124                    uf.merge_if_needs(size, v)125                else:126                    if not under_sea[ni][nj]:127                        continue128 129                    # 既に沈んでいる130                    uf.merge_if_needs(v, ni * w + nj)131 132        count = h * w - (uf.get_group_size(size) - 1)133        print(count)134 135 136if __name__ == "__main__":137    main()138