結果
問題 |
No.2290 UnUnion Find
|
ユーザー |
![]() |
提出日時 | 2023-06-11 01:16:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,275 ms / 2,000 ms |
コード長 | 986 bytes |
コンパイル時間 | 649 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 112,384 KB |
最終ジャッジ日時 | 2025-01-03 03:33:13 |
合計ジャッジ時間 | 42,413 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 46 |
ソースコード
# coding: utf-8 # Your code here! N,Q=map(int,input().split()) par = [i for i in range(N+1)] rank = [0]*(N+1) def find(x): if par[x] == x: return x else: par[x] = find(par[x]) #経路圧縮 return par[x] def same(x,y): return find(x) == find(y) def unite(x,y): x = find(x) y = find(y) if x == y: return 0 if rank[x] < rank[y]: par[x] = y else: par[y] = x if rank[x]==rank[y]:rank[x]+=1 is_par=set([i for i in range(N)]) def recog(n): if n in is_par: if find(n)!=n: is_par.remove(n) else: if find(n)==n: is_par.add(n) l,r=0,N-1 for _ in range(Q): q=input().split() if q[0]=="1": u,v=int(q[1])-1,int(q[2])-1 unite(u,v) while l!=find(l): l+=1 while r!=find(r): r-=1 else: v=int(q[1])-1 print(-1 if l==r else l+1 if same(v,r) else r+1)