結果
問題 | No.2290 UnUnion Find |
ユーザー |
|
提出日時 | 2023-05-05 21:51:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,366 bytes |
コンパイル時間 | 2,340 ms |
コンパイル使用メモリ | 207,616 KB |
最終ジャッジ日時 | 2025-02-12 18:01:20 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 TLE * 9 MLE * 9 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using Vi = std::vector<int> ;using Vl = vector<ll>;using VVi = vector<Vi>;class UnionFind {Vi par;Vi siz;Vl val;VVi iv;public :set<int> st;UnionFind(int N = 0) {par.resize(N);siz.resize(N);iv.resize(N);iota(par.begin(), par.end(), 0);fill(siz.begin(), siz.end(), 0);for (int i = 0; i < N; i ++) {iv[i].push_back(i);st.insert(i);}}void init(int N) {par.resize(N);siz.resize(N);iota(par.begin(), par.end(), 0);fill(siz.begin(), siz.end(), 0);}int root(int v) {if (v == par[v]) {return v;} else {return par[v] = root(par[v]);}}bool unit(int a, int b) {a = root(a);b = root(b);if (a == b) {return false;}if (siz[a] < siz[b]) {swap(a, b);}par[b] = a;siz[a] += siz[b];for (auto x : iv[b]) {iv[a].push_back(x);}st.erase(b);return true;}};int main () {int N, Q;cin >> N >> Q;UnionFind uu(N);while (Q--) {int t;cin >> t;if (t - 1) {int a;cin >> a;if (uu.st.size() == 1) {puts("-1");} else {a = uu.root(--a);if (a != *uu.st.begin()) {cout << (*uu.st.begin()) + 1 << endl;} else {cout << (*uu.st.rbegin()) + 1 << endl;}}} else {int a, b;cin >> a >> b;uu.unit(--a, --b);}}}