結果
問題 |
No.2290 UnUnion Find
|
ユーザー |
|
提出日時 | 2024-04-22 03:01:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 231 ms / 2,000 ms |
コード長 | 1,187 bytes |
コンパイル時間 | 996 ms |
コンパイル使用メモリ | 85,140 KB |
最終ジャッジ日時 | 2025-02-21 08:32:19 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 46 |
ソースコード
#include <iostream> #include <queue> #include<vector> #include<set> #include<stack> #include<array> #include<string> #include <cassert> #include <algorithm> using namespace std; #define ll long long #define endl "\n" const int N=2e5+10; int fa[N]; int find(int x){ if(fa[x]!=x) return fa[x]=find(fa[x]); return x; } void solved(){ int n,q; cin>>n>>q; set<int> s; for(int i=1;i<=n;i++){ fa[i]=i; s.insert(i); } while(q--){ int op; cin>>op; if(op==1){ int u,v; cin>>u>>v; if(find(u)==find(v)) continue; int fu=find(u),fv=find(v); s.erase(fv); fa[fv]=fu; } else{ int v; cin>>v; int fv=find(v); if(s.size()==1){ cout<<-1<<endl; } else{ int d1=*s.begin(),d2=*s.rbegin(); if(d1==fv){ cout<<d2<<endl; } else cout<<d1<<endl; } } } } signed main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); solved(); }