結果
問題 |
No.2290 UnUnion Find
|
ユーザー |
|
提出日時 | 2025-09-27 18:47:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 705 ms / 2,000 ms |
コード長 | 1,343 bytes |
コンパイル時間 | 4,187 ms |
コンパイル使用メモリ | 230,004 KB |
実行使用メモリ | 34,412 KB |
最終ジャッジ日時 | 2025-09-27 18:48:34 |
合計ジャッジ時間 | 34,874 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 46 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> #ifdef LOCAL #include <debug_print.hpp> #define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else #define debug(...) (static_cast<void>(0)) #endif using namespace atcoder; using mint=modint1000000007; using namespace std; using ll=long long; using ul=unsigned long long; using ld=long double; int dx[8] = {1, 0, -1, 0, -1, -1, 1, 1}; int dy[8] = {0, 1, 0, -1, -1, 1, -1, 1}; int main(){ int N,Q; cin>>N>>Q; dsu uf(N); vector<set<int>>st(N); set<int>stt; for(int i=0;i<N;i++)st[i].insert(i),stt.insert(i); while(Q--){ int t; cin>>t; if(t==1){ int u,v; cin>>u>>v; u--,v--; if(uf.same(u,v))continue; int U=uf.leader(u),V=uf.leader(v); uf.merge(u,v); if(uf.leader(u)==U){ for(auto k:st[V])st[U].insert(k),stt.erase(k); } else{ for(auto k:st[U])st[V].insert(k),stt.erase(k); } } else { int v; cin>>v; v--; if(stt.size()==1)cout<<-1<<endl; else{ stt.erase(uf.leader(v)); cout<<*stt.begin()+1<<endl; stt.insert(uf.leader(v)); } } } }