結果

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

ソースコード

diff # 

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * 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 = [{} for _ in range(N)]
    next_unconnected = [0] * N
    results = []
    
    for query in queries:
        if query[0] == 1:
            u, v = query[1] - 1, query[2] - 1
            if dsu.find(u) != dsu.find(v):
                dsu.union(u, v)
        
        elif query[0] == 2:
            v = query[1] - 1
            root_v = dsu.find(v)
            while next_unconnected[v] < N and (next_unconnected[v] == v or dsu.find(next_unconnected[v]) == root_v):
                next_unconnected[v] += 1
            
            if next_unconnected[v] >= N:
                results.append('-1')
            else:
                results.append(str(next_unconnected[v] + 1))
    
    return "\n".join(results)
import sys
input = sys.stdin.read
data = input().split()

idx = 0
N = int(data[idx])
Q = int(data[idx + 1])
idx += 2

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