結果
問題 | No.2290 UnUnion Find |
ユーザー |
![]() |
提出日時 | 2023-05-05 21:25:26 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 535 ms / 2,000 ms |
コード長 | 827 bytes |
コンパイル時間 | 4,292 ms |
コンパイル使用メモリ | 256,080 KB |
最終ジャッジ日時 | 2025-02-12 17:28:26 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 46 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using namespace std; using namespace atcoder; typedef modint998244353 mint; typedef long long ll; int main(){ int n, q; cin >> n >> q; dsu uf(n); set<int> alive; for (int i=0; i<n; i++){ alive.insert(i); } for (int i=0; i<q; i++){ int t; cin >> t; if (t == 1){ int u, v; cin >> u >> v; u--; v--; if (uf.same(u, v)) continue; int x = uf.leader(u); int y = uf.leader(v); alive.erase(x); alive.erase(y); uf.merge(u, v); int z = uf.leader(u); alive.insert(z); }else{ int u; cin >> u; u--; auto itr = alive.begin(); int k = *itr; if (k != uf.leader(u)){ cout << k+1 << "\n"; continue; } itr++; if (itr == alive.end()){ cout << -1 << "\n"; continue; } k = *itr; cout << k+1 << "\n"; } } }