結果
問題 | No.2290 UnUnion Find |
ユーザー | srjywrdnprkt |
提出日時 | 2023-05-13 01:59:33 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 435 ms / 2,000 ms |
コード長 | 1,825 bytes |
コンパイル時間 | 1,288 ms |
コンパイル使用メモリ | 117,408 KB |
実行使用メモリ | 15,744 KB |
最終ジャッジ日時 | 2024-11-28 22:06:51 |
合計ジャッジ時間 | 24,055 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 46 |
ソースコード
#include <iostream> #include <vector> #include <cmath> #include <map> #include <set> #include <iomanip> #include <queue> #include <algorithm> #include <numeric> #include <deque> using namespace std; struct UnionFind { vector<long long> par; vector<long long> siz; UnionFind(long long N) : par(N), siz(N) { for(long long i = 0; i < N; i++){ par[i] = i; siz[i] = 1; } } long long root(long long x) { if (par[x] == x) return x; return par[x] = root(par[x]); } long long unite(long long x, long long y) { long long rx = root(x); long long ry = root(y); if (rx == ry) return rx; if (siz[rx] > siz[ry]) swap(rx, ry); par[rx] = ry; siz[ry] += siz[rx]; return ry; } bool same(long long x, long long y) { long long rx = root(x); long long ry = root(y); return rx == ry; } long long size(long long x){ return siz[root(x)]; } }; int main(){ long long N, Q, t, x, y, xp, yp; cin >> N >> Q; UnionFind tree(N+1); set<long long> st; for (int i=1; i<=N; i++) st.insert(i); for (int i=0; i<Q; i++){ cin >> t; if (t == 1){ cin >> x >> y; xp = tree.root(x); yp = tree.root(y); if (xp == yp) continue; tree.unite(xp, yp); if (tree.root(xp) == yp) swap(xp, yp); st.erase(yp); } else{ cin >> x; xp = tree.root(x); if (st.size() == 1) cout << -1 << endl; else{ if (*st.begin() == xp) cout << *st.rbegin() << endl; else cout << *st.begin() << endl; } } } return 0; }