結果
問題 |
No.2290 UnUnion Find
|
ユーザー |
|
提出日時 | 2023-05-12 02:07:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 58 ms / 2,000 ms |
コード長 | 1,105 bytes |
コンパイル時間 | 1,924 ms |
コンパイル使用メモリ | 196,408 KB |
最終ジャッジ日時 | 2025-02-12 21:25:40 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 46 |
ソースコード
#include<bits/stdc++.h> using namespace std; constexpr int INPUT_MAX=200005; int rt[INPUT_MAX]; int sz[INPUT_MAX]; int getroot(int n){ if(rt[n]==-1)return n; return rt[n]=getroot(rt[n]); } void unite(int a,int b){ a=getroot(a),b=getroot(b); if(a!=b){ rt[a]=b; sz[b]+=sz[a]; } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); fill(rt,rt+INPUT_MAX,-1); fill(sz,sz+INPUT_MAX,1); int N,Q; cin>>N>>Q; int NG=Q; vector<array<int,2>>output; for(int i=0;i<Q;i++){ int p; cin>>p; if(p==1){ int a,b; cin>>a>>b; --a,--b; if(getroot(a)!=getroot(b)&&sz[getroot(a)]+sz[getroot(b)]==N){ NG=i; }else{ unite(a,b); } }else{ int v; cin>>v; output.push_back({i,v-1}); } } array<int,2>rrr={-1,-1}; for(int i=0;i<N;i++){ int t=getroot(i); if(rrr[0]==-1){ rrr[0]=t; }else if(rrr[1]==-1&&rrr[0]!=t){ rrr[1]=t; } } for(auto [i,j]:output){ if(i>=NG){ cout<<"-1\n"; }else{ cout<<(getroot(j)==rrr[0]?rrr[1]:rrr[0])+1<<'\n'; } } }