結果

問題 No.2290 UnUnion Find
コンテスト
ユーザー NP
提出日時 2024-07-04 21:37:04
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,852 bytes
コンパイル時間 217 ms
コンパイル使用メモリ 82,032 KB
実行使用メモリ 147,956 KB
最終ジャッジ日時 2024-07-04 21:37:11
合計ジャッジ時間 5,335 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 TLE * 1 -- * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [1] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        
        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1

def process_queries(N, Q, queries):
    dsu = DSU(N)
    connected = [set() for _ in range(N)]
    
    results = []
    
    for query in queries:
        if query[0] == 1:
            u = query[1] - 1
            v = query[2] - 1
            dsu.union(u, v)
            connected[u].add(v)
            connected[v].add(u)
        elif query[0] == 2:
            v = query[1] - 1
            found = False
            for i in range(N):
                if i != v and i not in connected[v] and dsu.find(i) != dsu.find(v):
                    results.append(str(i + 1))
                    found = True
                    break
            if not found:
                results.append('-1')
    
    return "\n".join(results)

import sys
input = sys.stdin.read
data = input().split()

N = int(data[0])
Q = int(data[1])
queries = []

index = 2
for _ in range(Q):
    query_type = int(data[index])
    if query_type == 1:
        u = int(data[index + 1])
        v = int(data[index + 2])
        queries.append([1, u, v])
        index += 3
    elif query_type == 2:
        v = int(data[index + 1])
        queries.append([2, v])
        index += 2
print(process_queries(N, Q, queries))
0