Submission #27896127

---

Source Code Expand

import math
import random
import copy
import typing
from typing import List, Tuple


class Coordinate:
    """
    2次元平面上の座標を表すクラス。
    """

    def __init__(self, x: int, y: int):
        self.x = x
        self.y = y

    def get_dist(self, other):
        dx = self.x - other.x
        dy = self.y - other.y
        dist = int(round(math.sqrt(dx * dx + dy * dy)))
        return dist


class Testcase:
    """
    テストケースの入力を表すクラス。
    """

    def __init__(
        self,
        n: int,
        m: int,
        coordinates: List[Coordinate],
        edges: List[Tuple[int, int]],
    ):
        self.n = n
        self.m = m
        self.coordinates = coordinates
        self.edges = edges


class DSU:
    """
    いわゆるUnion-Find。
    https://github.com/not522/ac-library-python/blob/master/atcoder/dsu.py

    Implement (union by size) + (path halving)
    Reference:
    Zvi Galil and Giuseppe F. Italiano,
    Data structures and algorithms for disjoint set union problems
    """

    def __init__(self, n: int = 0) -> None:
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a: int, b: int) -> int:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        x = self.leader(a)
        y = self.leader(b)

        if x == y:
            return x

        if -self.parent_or_size[x] < -self.parent_or_size[y]:
            x, y = y, x

        self.parent_or_size[x] += self.parent_or_size[y]
        self.parent_or_size[y] = x

        return x

    def same(self, a: int, b: int) -> bool:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        return self.leader(a) == self.leader(b)

    def leader(self, a: int) -> int:
        assert 0 <= a < self._n

        parent = self.parent_or_size[a]
        while parent >= 0:
            if self.parent_or_size[parent] < 0:
                return parent
            self.parent_or_size[a], a, parent = (
                self.parent_or_size[parent],
                self.parent_or_size[parent],
                self.parent_or_size[self.parent_or_size[parent]],
            )

        return a

    def size(self, a: int) -> int:
        assert 0 <= a < self._n

        return -self.parent_or_size[self.leader(a)]

    def groups(self) -> typing.List[typing.List[int]]:
        leader_buf = [self.leader(i) for i in range(self._n)]

        result: typing.List[typing.List[int]] = [[] for _ in range(self._n)]
        for i in range(self._n):
            result[leader_buf[i]].append(i)

        return list(filter(lambda r: r, result))


def main() -> None:
    """
    メイン関数。テストケースを読み込んで解く。
    """
    testcase = read_testcase()
    solve(testcase)


def read_testcase() -> Testcase:
    """
    テストケースを読み込む。
    """

    # 固定値
    N = 400
    M = 1995

    # 点の座標(x, y)の読み込み
    coordinates = []
    for _ in range(N):
        x, y = map(int, input().split())
        coordinate = Coordinate(x, y)
        coordinates.append(coordinate)

    # 辺(u, v)の読み込み
    edges = []
    for _ in range(M):
        u, v = map(int, input().split())
        edges.append((u, v))

    testcase = Testcase(N, M, coordinates, edges)
    return testcase


def solve(testcase: Testcase) -> None:
    """
    問題を解く。
    """
    # ランダムな辺のリストを何セット作成するか
    EDGE_SET_COUNT = 1

    # 乱数のシード値
    RANDOM_SEED = 42

    # ランダムな辺のリストを生成
    random_dists_all = generate_random_dists(testcase, EDGE_SET_COUNT, RANDOM_SEED)

    # 頂点の連結状態を管理するUnion-Find
    union_find = DSU(testcase.n)

    # 各辺について採用するかしないか判断していく
    for edge_index in range(testcase.m):
        # i番目の辺の長さ
        edge_distance = int(input())

        # 採用するかしないか判断
        use = decide_use_or_not(
            testcase, edge_index, edge_distance, union_find, random_dists_all
        )

        if use:
            u, v = testcase.edges[edge_index]
            union_find.merge(u, v)
            print(1)
        else:
            print(0)


def decide_use_or_not(
    testcase: Testcase,
    edge_index: int,
    edge_distance: int,
    union_find: DSU,
    random_dists_all: List[List[int]],
) -> bool:
    """
    edge_index番目の辺について、採用するかしないか判断する。
    """
    u, v = testcase.edges[edge_index]

    # 既に連結だったら採用しない
    if union_find.same(u, v):
        return False

    # 採用した回数・しなかった回数
    use_count = 0
    pass_count = 0

    for random_dists in random_dists_all:
        # edge_index 番目の辺のコストを実際の値で上書き
        random_dists[edge_index] = edge_distance

        # 採用するかどうかをクラスカル法により判断する
        union_find_copied = copy.deepcopy(union_find)
        use = kruskal(testcase, union_find_copied, edge_index, random_dists)

        if use:
            use_count += 1
        else:
            pass_count += 1

    # 多数決で決める
    use = use_count >= pass_count
    return use


def generate_random_dists(
    testcase: Testcase, count: int, random_seed: int
) -> List[List[int]]:
    """
    ランダムな辺の長さのリストをcount個生成する。
    各辺の長さは、辺のユークリッド距離をdとしてd以上3d以下のランダムな値とする。
    """
    # シードの設定
    random.seed(random_seed)

    # ユークリッド距離を求めておく
    euclidean_dists = calc_euclidean_dists(testcase)

    # 辺の長さのリストのリスト
    # M要素のリストがcount個入った2次元リストとなる
    random_dists_all = []

    for _ in range(count):
        # 辺の長さのリスト（1ケース分）
        random_dists = []

        for euclidean_dist in euclidean_dists:
            # d以上3d以下の範囲でランダムに辺の長さを決める
            dist = random.randint(euclidean_dist, 3 * euclidean_dist)
            random_dists.append(dist)

        random_dists_all.append(random_dists)

    return random_dists_all


def calc_euclidean_dists(testcase: Testcase) -> List[int]:
    """
    全ての辺のユークリッド距離を計算する。
    """
    distances = []

    for u, v in testcase.edges:
        p = testcase.coordinates[u]
        q = testcase.coordinates[v]
        dist = p.get_dist(q)
        distances.append(dist)

    return distances


def kruskal(
    testcase: Testcase, union_find: DSU, edge_index: int, distances: List[int]
) -> bool:
    """
    クラスカル法により最小全域木問題を解き、edge_index番目の辺を使ったかどうかを返す。
    """
    # edge_index番目以降の辺をコストの昇順にソート
    edge_indice = sorted(range(edge_index, testcase.m), key=lambda i: distances[i])

    # edge_index番目の辺を使ったかどうか
    used = False

    # マージしていく（普通のクラスカル法）
    for i in edge_indice:
        u, v = testcase.edges[i]

        if not union_find.same(u, v):
            union_find.merge(u, v)

            # edge_index番目を使った場合
            if i == edge_index:
                used = True

    return used


main()

Submission Info

Judge Result