結果

問題 No.2652 [Cherry 6th Tune N] Δρονε χιρχλινγ
ユーザー LyricalMaestro
提出日時 2025-07-04 23:45:36
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,117 bytes
コンパイル時間 613 ms
コンパイル使用メモリ 82,048 KB
実行使用メモリ 259,196 KB
最終ジャッジ日時 2025-07-04 23:46:17
合計ジャッジ時間 39,418 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 3 TLE * 8 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2292

from collections import deque

class UnionFind:
    """
    UnionFindの基本的な処理を実装したクラス
    """

    def __init__(self, size):
        self.root = [i for i in range(size)]
        self.size = [1] * size

    def get_root(self, v):
        if v == self.root[v]:
            return v
        else:
            old_root = self.root[v]
            new_root = self.get_root(old_root)
            self.root[v] = new_root
            return new_root

    def merge(self, u, v):
        root_u = self.get_root(u)
        root_v = self.get_root(v)
        if root_u == root_v:
            return False

        if self.size[root_u] >= self.size[root_v]:
            self.size[root_u] += self.size[root_v]
            self.root[root_v] = root_u
            self.root[v] = root_u
        else:
            self.size[root_v] += self.size[root_u]
            self.root[root_u] = root_v
            self.root[u] = root_v
        return True
    

def solve(N, L, xy):
    uv = []
    for i in range(N):
        x, y = xy[i]
        u = x + y
        v = x - y
        uv.append((u, v, i))

    uv.sort(key=lambda x : x[0])

    edges = []
    for j in range(N - 1):
        u1, v1, i1 = uv[j]
        u2, v2, i2 = uv[j + 1]
        u = abs(u1 - u2)
        v = abs(v1 - v2)
        edges.append((u, i1, i2))
        edges.append((v, i1, i2))

    uv.sort(key=lambda x : x[1])
    edges = []
    for j in range(N - 1):
        u1, v1, i1 = uv[j]
        u2, v2, i2 = uv[j + 1]
        u = abs(u1 - u2)
        v = abs(v1 - v2)
        edges.append((u, i1, i2))
        edges.append((v, i1, i2))
    
    edges.sort(key=lambda x: x[0])

    appeared = set()
    uf = UnionFind(N)
    next_edges = [[] for _ in range(N)]
    cost = 0
    for u, i1, i2 in edges:
        i00 = min(i1, i2)
        i01 = max(i1, i2)
        k = i00 * N + i01
        if k not in appeared:
            appeared.add(k)
        else:
            if uf.merge(i1, i2):
                next_edges[i1].append(i2)
                next_edges[i2].append(i1)
                cost += u
    
    stack = deque()
    stack.append((0, 0))
    parents = [-2] * N
    parents[0] = -1
    array = []
    while len(stack) > 0:
        v, index = stack.pop()
        array.append(v)

        while index < len(next_edges[v]):
            w = next_edges[v][index]
            if w == parents[v]:
                index +=1
                continue

            parents[w] = v
            stack.append((v, index + 1))
            stack.append((w, 0))
            break

    answer= [len(array)]
    for i in range(len(array)):
        answer.append(" ".join(map(str, xy[array[i]])))
    return answer


def main():
    T = int(input())
    answers = []
    for _ in range(T):
        N, L = map(int, input().split())
        xy = []
        for _ in range(N):
            x, y = map(int, input().split())
            xy.append((x, y))
        ans = solve(N,L,  xy)
        answers.append(ans)

    for ans in answers:
        for a in ans:
            print(a)









if __name__ == "__main__":
    main()
0