結果
| 問題 |
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));
}
}
}
}