結果

問題 No.2290 UnUnion Find
ユーザー NPNP
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
59,552 KB
testcase_01 AC 40 ms
52,608 KB
testcase_02 AC 143 ms
120,704 KB
testcase_03 TLE -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
testcase_45 -- -
testcase_46 -- -
権限があれば一括ダウンロードができます

ソースコード

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